15-122: Principles of Imperative Computation.

 
15-122: Principles of
Imperative Computation
 
L
e
c
t
u
r
e
 
2
4
:
 
P
r
i
o
r
i
t
y
 
Q
u
e
u
e
s
 
A
p
r
i
l
 
1
7
,
 
2
0
2
3
 
Today…
 
Last lecture
:
Graph Search: DFS and BFS
 
Today’s lecture
:
Priority queues: heaps, adding to heaps, removing from heaps,
and representing heaps
 
Announcements
:
Last written assignment is due today by 9PM
Last programming assignment is due tomorrow by 9PM (
you can
use 2 extra grace days for this assignment
)
The final exam is on Sunday, April 30 from 8:30AM to 11:30AM in
Room 2163
 
 
 
1
 
W
o
r
k
 
l
i
s
t
s
:
 
D
a
t
a
 
s
t
r
u
c
t
u
r
e
s
 
t
h
a
t
o
Store elements and
o
Give them back one at a time – in some order
 
S
t
a
c
k
s
:
 
R
e
t
r
i
e
v
e
 
t
h
e
 
e
l
e
m
e
n
t
 
t
h
a
t
 
w
a
s
 
i
n
s
e
r
t
e
d
 
m
o
s
t
r
e
c
e
n
t
l
y
 
Q
u
e
u
e
s
:
 
R
e
t
r
i
e
v
e
 
t
h
e
 
e
l
e
m
e
n
t
 
t
h
a
t
 
h
a
s
 
b
e
e
n
 
t
h
e
r
e
 
l
o
n
g
e
s
t
 
P
r
i
o
r
i
t
y
 
q
u
e
u
e
s
:
 
R
e
t
r
i
e
v
e
t
h
e
 
m
o
s
t
 
i
n
t
e
r
e
s
t
i
n
g
 
e
l
e
m
e
n
t
Review
Today
2
The Work List Interface
Recall the work list interface template:
typedef 
void* elem
;
          // Decided by client
// typedef ______* wl_t;
bool
 
wl_empty
(
wl_t
 
W
)
  /*@requires W != NULL;
 
@*/
 ;
wl_t 
wl_new
()
  /*@ensures \result != NULL &&  wl_empty(\result);
 
@*/
 ;
void
 
wl_add
(
wl_t
 
W
, 
elem 
e
)
  /*@requires W != NULL && e != NULL;
 
@*/
  /*@ensures !wl_empty(W);
 
@*/
 ;
elem 
wl_retrieve
(
wl_t 
W
)
  /*@requires W != NULL && !wl_empty(W);
 
@*/
  /*@requires \result != NULL;
 
@*/
 ;
W
o
r
k
 
L
i
s
t
 
I
n
t
e
r
f
a
c
e
Now,
fully generic
This is not the
interface of an actual
data structure but
a general template
for the work lists
we are studying
3
 
P
r
i
o
r
i
t
y
 
Q
u
e
u
e
s
 
4
Priority Queues
 
Retrieve the most “interesting” element
o
E
l
e
m
e
n
t
s
 
a
r
e
 
g
i
v
e
n
 
p
r
i
o
r
i
t
i
e
s
o
R
e
t
r
i
e
v
e
 
t
h
e
 
e
l
e
m
e
n
t
 
w
i
t
h
 
t
h
e
 
h
i
g
h
e
s
t
 
p
r
i
o
r
i
t
y
o
Several elements may have the same priority
 
Examples:
o
Emergency room
Highest priority = most severe condition
o
Processes in an OS
Highest priority = 
well, it’s complicated
o
Homework due
Highest priority = …
5
Towards a Priority Queue Interface
 
It will be convenient
to have
a 
peek
function
o
It returns
the highest
priority
element
without
removing it
typedef 
void* elem
;
          // Decided by client
// typedef ______* pq_t;
bool
 
pq_empty
(
pq_t
 
Q
)
  /*@requires Q != NULL;
 
@*/
 ;
pq_t 
pq_new
()
  /*@ensures \result != NULL &&  pq_empty(\result);
 
@*/
 ;
void
 
pq_add
(
pq_t
 
Q
, 
elem 
e
)
  /*@requires Q != NULL && e != NULL;
 
@*/
  /*@ensures !pq_empty(Q);
 
@*/
 ;
elem 
pq_rem 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
 
  /*@ensures \result != NULL;
 
@*/
 ;
elem 
pq_peek 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
  /*@ensures \result != NULL && !pq_empty(Q);
 
@*/
 ;
P
r
i
o
r
i
t
y
 
Q
u
e
u
e
 
I
n
t
e
r
f
a
c
e
This is the
work list interface
with names changed
Added
6
How to Specify Priorities?
 
1.
Mention it as part of 
pq_add
 
  
void
 
pq_add
(
pq_t
 
Q
, 
elem 
e
,  
int 
priority
)
 
o
How do we assign a priority to an element?
The same element should always be given the same priority
Priorities should form some kind of order
o
Do bigger numbers represent higher or lower priorities?
 
Potential for
lots of errors
 
People are bad
at being
consistent
7
How to Specify Priorities?
 
2.
Make the priority part of an 
elem
o
And provide a way to retrieve it
 
  
int
 
get_priority
(
elem 
e
)
 
o
How do we assign a priority to an element?
The same element should always be given the same priority
Priorities should form some kind of order
o
Do bigger numbers represent higher or lower priorities?
 
Same issues
as (1)
 
Same issues
as (1)
The problem is that assigning
a priority to an element is hard
for people
But given two elements,
saying which one has
higher priority is easier
8
How to Specify Priorities?
 
3.
Have a way to tell which of two elements has higher priority
 
  
bool
 
has_higher_priority
(
elem 
e1
,
 elem 
e2
)
 
o
I
t
 
r
e
t
u
r
n
s
 
t
r
u
e
 
i
f
 
e
1
 
h
a
s
 
s
t
r
i
c
t
l
y
 
h
i
g
h
e
r
 
p
r
i
o
r
i
t
y
 
t
h
a
n
 
e
2
 
o
It is the client who should provide this function
Only they know what 
elem
 is
 
o
F
o
r
 
t
h
e
 
p
r
i
o
r
i
t
y
 
q
u
e
u
e
 
l
i
b
r
a
r
y
 
t
o
 
b
e
 
g
e
n
e
r
i
c
,
 
w
e
 
t
u
r
n
 
i
t
 
i
n
t
o
 
a
t
y
p
e
 
d
e
f
i
n
i
t
i
o
n
 
t
y
p
e
d
e
f
 
b
o
o
l
 
h
a
s
_
h
i
g
h
e
r
_
p
r
i
o
r
i
t
y
_
f
n
(
e
l
e
m
 
e
1
,
 
e
l
e
m
 
e
2
)
;
 
 
and have 
pq_new
 take a priority function as input
 
Given two elements,
saying which one has
higher priority is easier
9
The Priority Queue Interface
typedef 
void* elem
;
          // Decided by client
t
y
p
e
d
e
f
 
b
o
o
l
 
h
a
s
_
h
i
g
h
e
r
_
p
r
i
o
r
i
t
y
_
f
n
(
e
l
e
m
 
e
1
,
 
e
l
e
m
 
e
2
)
;
// typedef ______* pq_t;
bool
 
pq_empty
(
pq_t
 
Q
)
  /*@requires Q != NULL;
 
@*/
 ;
pq_t 
pq_new
(
has_higher_priority_fn*
 prio
)
  /*@requires prio != NULL; @*/
  /*@ensures \result != NULL &&  pq_empty(\result);
 
@*/
 ;
void
 
pq_add
(
pq_t
 
Q
, 
elem 
e
)
  /*@requires Q != NULL && e != NULL;
 
@*/
  /*@ensures !pq_empty(Q);
 
@*/
 ;
elem 
pq_rem 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
 
  /*@ensures \result != NULL;
 
@*/
 ;
elem 
pq_peek 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
  /*@ensures \result != NULL && !pq_empty(Q);
 
@*/
 ;
P
r
i
o
r
i
t
y
 
Q
u
e
u
e
 
I
n
t
e
r
f
a
c
e
We commit to the
priority function when
creating the queue
f
(
e
1
,
 
e
2
)
 
r
e
t
u
r
n
s
 
t
r
u
e
 
i
f
 
e
1
h
a
s
 
s
t
r
i
c
t
l
y
 
h
i
g
h
e
r
 
p
r
i
o
r
i
t
y
t
h
a
n
 
e
2
10
 
Priority Queue Implementations
C
o
s
t
 
o
f
 
a
d
d
u
s
i
n
g
 
a
r
r
a
y
s
 
a
r
e
a
m
o
r
t
i
z
e
d
11
 
H
e
a
p
s
 
12
Heaps
 
A
 
h
e
a
p
 
i
s
 
a
 
t
y
p
e
 
o
f
 
b
i
n
a
r
y
 
t
r
e
e
 
u
s
e
d
 
t
o
 
i
m
p
l
e
m
e
n
t
 
p
r
i
o
r
i
t
y
q
u
e
u
e
s
 
S
i
n
c
e
 
a
d
d
 
a
n
d
 
r
e
m
 
h
a
v
e
 
c
o
s
t
 
O
(
l
o
g
 
n
)
,
a
 
h
e
a
p
 
i
s
 
a
 
b
a
l
a
n
c
e
d
 
b
i
n
a
r
y
 
t
r
e
e
o
In fact, they are as balanced as a tree can be
 
Since 
peek
 has cost O(1), the highest
priority element must be at the root
o
In fact, the elements on any path from a
leaf to the root are ordered in increasing
priority order
 
highest
priority
 
lower
priority
Nothing to do with
the memory segment
13
Heaps Invariants
 
1.
S
h
a
p
e
 
i
n
v
a
r
i
a
n
t
 
 
 
 
2.
O
r
d
e
r
i
n
g
 
i
n
v
a
r
i
a
n
t
o
The priority of a child is lower than
or equal to the priority of its parent
    
or equivalently
o
The priority of a parent is higher than
or equal to the priority of its children
 
higher priority
P
o
i
n
t
 
o
f
 
v
i
e
w
o
f
 
c
h
i
l
d
P
o
i
n
t
 
o
f
 
v
i
e
w
o
f
 
p
a
r
e
n
t
Both points of view
will come handy
14
The Many Things Called Heaps
 
A
 
h
e
a
p
 
i
s
 
a
 
t
y
p
e
 
o
f
 
b
i
n
a
r
y
 
t
r
e
e
 
u
s
e
d
 
t
o
 
i
m
p
l
e
m
e
n
t
 
p
r
i
o
r
i
t
y
q
u
e
u
e
s
 
A
 
h
e
a
p
 
i
s
 
a
l
s
o
 
a
n
y
 
p
r
i
o
r
i
t
y
 
q
u
e
u
e
 
w
h
e
r
e
 
p
r
i
o
r
i
t
i
e
s
 
a
r
e
i
n
t
e
g
e
r
s
o
I
t
 
i
s
 
a
 
m
i
n
-
h
e
a
p
 
i
f
 
s
m
a
l
l
e
r
 
n
u
m
b
e
r
s
 
r
e
p
r
e
s
e
n
t
 
h
i
g
h
e
r
 
p
r
i
o
r
i
t
i
e
s
o
I
t
 
i
s
 
a
 
m
a
x
-
h
e
a
p
 
i
f
 
b
i
g
g
e
r
 
n
u
m
b
e
r
s
 
r
e
p
r
e
s
e
n
t
 
h
i
g
h
e
r
 
p
r
i
o
r
i
t
i
e
s
 
A
 
h
e
a
p
 
i
s
 
t
h
e
 
s
e
g
m
e
n
t
 
o
f
 
m
e
m
o
r
y
 
w
e
 
c
a
l
l
e
d
 
a
l
l
o
c
a
t
e
d
m
e
m
o
r
y
This is a significant
source of confusion
15
Min-heaps
 
Any priority queue where priorities are integers and
s
m
a
l
l
e
r
 
n
u
m
b
e
r
s
 
r
e
p
r
e
s
e
n
t
 
h
i
g
h
e
r
 
p
r
i
o
r
i
t
i
e
s
 
In practice, most priority queues are implemented as
min-heaps
o
A
n
d
 
h
e
a
p
 
i
s
 
a
l
s
o
 
s
h
o
r
t
h
a
n
d
 
f
o
r
 
m
i
n
-
h
e
a
p
 
Most of our examples will be min-heaps
1.
Shape invariant
2.
Ordering invariant
T
h
e
 
v
a
l
u
e
 
o
f
 
a
 
c
h
i
l
d
 
i
s
 
 
t
h
e
 
v
a
l
u
e
 
o
f
 
i
t
s
 
p
a
r
e
n
t
   
or equivalently
T
h
e
 
v
a
l
u
e
 
o
f
 
a
 
p
a
r
e
n
t
 
i
s
 
 
t
h
e
 
v
a
l
u
e
 
o
f
 
i
t
s
 
c
h
i
l
d
r
e
n
more confusion!
 
larger value
16
 
Activity
 
Draw a min-heap with values 1, 2, 2, 9, 7
 
17
 
Activity
 
Draw a min-heap with values 1, 2, 2, 9, 7
 
… and several more
 
18
 
I
n
s
e
r
t
i
o
n
 
i
n
t
o
 
a
 
H
e
a
p
 
19
Insertion Strategy
 
Maintain the shape invariant
 
Temporary break and then
restore the ordering invariant
larger value
Min-heap version
This is similar to what we did for AVL trees
Maintain the ordering invariant
Temporary break and then restore the height invariant
20
Example
 
We start by putting the new element in the only place that
maintains the shape invariant
o
But doing so may break the ordering invariant
 
 
 
 
 
 
 
 
o
H
o
w
 
t
o
 
f
i
x
 
i
t
?
I
nsert 1
1 must go here
This is a min-heap
This 
violates
 the
ordering invariant
21
Swapping Up
 
How to fix the violation?
o
Swap the child with the parent
 
 
 
 
 
 
 
 
 
o
Swapping up may introduce
a new violation
S
wap up
We swapped
7 and 1
This introduced a new 
violation
 of
the ordering invariant one level up
22
Swapping Up
 
How to fix the violation?
o
Swap the child with the parent
 
 
 
 
 
 
 
 
We stop when no new violation
is introduced
o
Or we reach the root
S
wap up
We swapped
2 and 1
There are no more violations.
This is a valid min-heap
23
Adding an Element
 
General procedure
1.
Put the added element in the one place that
maintains the shape invariant
The leftmost open slot on the last level
Or, if the last level is full, the leftmost slot on the next level
2.
Repeatedly swap it up with its parent
Until the violation is fixed
Or we reach the root
o
T
h
e
r
e
 
i
s
 
a
l
w
a
y
s
 
a
t
 
m
o
s
t
 
o
n
e
 
v
i
o
l
a
t
i
o
n
 
T
h
e
 
o
v
e
r
a
l
l
 
p
r
o
c
e
s
s
 
i
s
 
c
a
l
l
e
d
 
s
i
f
t
i
n
g
 
u
p
 
This costs 
O(log n)
o
Because we make at most 
O(log n)
 swaps
For a heap with 
n
 elements
 
 
24
 
R
e
m
o
v
i
n
g
 
t
h
e
 
M
i
n
i
m
a
l
 
E
l
e
m
e
n
t
 
o
f
 
a
 
H
e
a
p
 
25
Deletion Strategy
 
Maintain the shape invariant
 
Temporary break and then
restore the ordering invariant
larger value
Min-heap version
Same as insertion
26
Example
 
We must return the root
And replace it with the only element that maintains the
shape invariant
 
 
 
 
 
 
 
 
W
h
i
c
h
 
v
i
o
l
a
t
i
o
n
 
t
o
 
f
i
x
 
f
i
r
s
t
?
R
em
We must return 1
We replace it with 9
T
h
i
s
 
c
a
u
s
e
s
t
w
o
 
v
i
o
l
a
t
i
o
n
s
T
h
i
s
 
c
a
u
s
e
s
t
w
o
 
v
i
o
l
a
t
i
o
n
s
27
Swapping Down
 
Which violation to fix first?
o
I
f
 
w
e
 
s
w
a
p
 
4
 
a
n
d
 
9
,
 
w
e
 
e
n
d
 
u
p
 
w
i
t
h
 
t
h
r
e
e
 
v
i
o
l
a
t
i
o
n
s
 
 
 
 
 
 
 
 
Can we do better?
 
S
wap down
28
Swapping Down
 
I
f
 
w
e
 
s
w
a
p
 
9
 
a
n
d
 
2
,
 
w
e
 
e
n
d
 
u
p
 
w
i
t
h
 
o
n
e
 
v
i
o
l
a
t
i
o
n
o
At most two in general
 
 
 
 
 
 
 
W
h
e
n
 
s
w
a
p
p
i
n
g
 
d
o
w
n
,
 
a
l
w
a
y
s
 
s
w
a
p
 
w
i
t
h
 
t
h
e
 
c
h
i
l
d
 
w
i
t
h
t
h
e
 
h
i
g
h
e
s
t
 
p
r
i
o
r
i
t
y
o
Smallest value in a min-heap
S
wap
 
d
own
29
Swapping Down
 
Always swap the child with the highest priority
 
 
 
 
 
 
 
 
We stop when no new violations are introduced
o
Or we reach a leaf
S
wap down
30
Removing an Element
 
General procedure
1.
Return the root
2.
Replace it with the element in the one
place that maintains the shape invariant
The rightmost element on the last level
3.
Repeatedly swap it down with its child that has highest priority
Until all violations are fixed
Or we reach a leaf
o
T
h
i
s
 
g
u
a
r
a
n
t
e
e
s
 
t
h
e
r
e
 
a
r
e
 
a
l
w
a
y
s
 
a
t
 
m
o
s
t
 
t
w
o
 
v
i
o
l
a
t
i
o
n
s
 
T
h
e
 
o
v
e
r
a
l
l
 
p
r
o
c
e
s
s
 
i
s
 
c
a
l
l
e
d
 
s
i
f
t
i
n
g
 
d
o
w
n
 
This costs 
O(log n)
o
Because we make at most 
O(log n)
 swaps
For a heap with 
n
 elements
 
 
31
 
Priority Queue Implementations
C
o
s
t
 
o
f
 
a
d
d
u
s
i
n
g
 
a
r
r
a
y
s
 
a
r
e
a
m
o
r
t
i
z
e
d
 
32
 
R
e
p
r
e
s
e
n
t
i
n
g
 
H
e
a
p
s
 
33
How to Represent a Heap?
 
Borrowing from BSTs,
we could use pointers
o
left
 child and 
right
 child
Needed when sifting down
o
parent
 node
Needed when sifting up
 
 
That’s a lot of pointers to keep track of!
o
It also takes up a lot of space
 
 
Can we do better?
2
4
4
7
 
parent
 
left
 
right
typedef struct 
heap_node heap
;
struct
 
heap_node 
{
  elem 
data;
  
heap* 
parent;
  
heap* 
left;
  
heap* 
right;
};
Try writing the swap function!
 
34
Understanding Heaps
 
Let’s 
number the nodes 
level by level starting at 1
 
 
 
 
 
 
 
Observations:
o
I
f
 
a
 
n
o
d
e
 
h
a
s
 
n
u
m
b
e
r
 
i
,
 
i
t
s
 
l
e
f
t
 
c
h
i
l
d
 
h
a
s
 
n
u
m
b
e
r
o
I
f
 
a
 
n
o
d
e
 
h
a
s
 
n
u
m
b
e
r
 
i
,
 
i
t
s
 
r
i
g
h
t
 
c
h
i
l
d
 
h
a
s
 
n
u
m
b
e
r
o
I
f
 
a
 
n
o
d
e
 
h
a
s
 
n
u
m
b
e
r
 
i
,
 
i
t
s
 
p
a
r
e
n
t
 
h
a
s
 
n
u
m
b
e
r
 
1
 
2
 
3
 
6
 
4
 
5
 
2
i
 
2
i
 
+
 
1
 
i
/
2
35
Understanding Heaps
 
 
 
 
 
 
 
o
I
f
 
a
 
n
o
d
e
 
h
a
s
 
n
u
m
b
e
r
 
i
,
 
i
t
s
 
l
e
f
t
 
c
h
i
l
d
 
h
a
s
 
n
u
m
b
e
r
2
i
o
I
f
 
a
 
n
o
d
e
 
h
a
s
 
n
u
m
b
e
r
 
i
,
 
i
t
s
 
r
i
g
h
t
 
c
h
i
l
d
 
h
a
s
 
n
u
m
b
e
r
2
i
 
+
 
1
o
I
f
 
a
 
n
o
d
e
 
h
a
s
 
n
u
m
b
e
r
 
i
,
 
i
t
s
 
p
a
r
e
n
t
 
h
a
s
 
n
u
m
b
e
r
i
/
2
 
B
y
 
n
u
m
b
e
r
i
n
g
 
n
o
d
e
s
 
t
h
i
s
 
w
a
y
,
 
w
e
 
c
a
n
 
n
a
v
i
g
a
t
e
 
t
h
e
 
t
r
e
e
 
u
p
a
n
d
 
d
o
w
n
 
u
s
i
n
g
 
a
r
i
t
h
m
e
t
i
c
36
 
Understanding Heaps
 
 
 
 
 
 
 
By numbering nodes this way, we can navigate the tree up
and down using arithmetic
 
T
h
e
s
e
 
n
u
m
b
e
r
s
 
a
r
e
 
c
o
n
t
i
g
u
o
u
s
 
a
n
d
 
s
t
a
r
t
 
a
t
 
1
 
37
Understanding Heaps
 
 
 
 
 
 
 
These numbers are contiguous and start at 1
 
Do we know of any data structure that allows accessing
data based on consecutive integers?
 
A
r
r
a
y
s
!
38
Representing Heaps using Arrays
 
For simplicity, 
we do not use index 0
If a node has number 
i
, its 
left child 
has number
 
2i
If a node has number 
i
, its 
right child 
has number
 
2i + 1
if a node has number 
i
, its 
parent
 has number
 
i/2
39
Representing Heaps using Arrays
 
add
 will initially put a new element at index 7
40
Representing Heaps using Arrays
 
add
 will initially put a new element at index 7
remove
 will yank the element at index 6
We are better off
having unused positions
41
 
Concrete Type
 
The heap data structure needs to store
o
the array that contains the heap elements
o
its true size
o
the position where to add the next element
o
the priority function
typedef struct 
heap_header heap
;
struct
 
heap_header 
{
  
int
 limit;
  
elem[] 
data;
 
// \length(data) == limit
  
int
 next;
 
// 1 <= next  && next <= limit
 
has_higher_priority_fn*
 
prior;
 
 
// != NULL
};
We are better off
having unused positions
 
42
 
B
o
u
n
d
e
d
 
P
r
i
o
r
i
t
y
 
Q
u
e
u
e
s
 
43
Types of Work Lists
 
T
h
e
 
w
o
r
k
 
l
i
s
t
s
 
w
e
 
c
o
n
s
i
d
e
r
e
d
s
o
 
f
a
r
 
w
e
r
e
 
u
n
b
o
u
n
d
e
d
o
There was no maximum to the
number of elements they could
hold
 
A
 
b
o
u
n
d
e
d
 
w
o
r
k
 
l
i
s
t
 
h
a
s
 
a
c
a
p
a
c
i
t
y
 
f
i
x
e
d
 
a
t
 
c
r
e
a
t
i
o
n
 
t
i
m
e
o
We can’t add elements once full
 
In practice
o
Stacks are typically unbounded
o
Queues can be either
o
Priority queues are often bounded
typedef 
void* elem
;
          // Decided by client
t
y
p
e
d
e
f
 
b
o
o
l
 
h
a
s
_
h
i
g
h
e
r
_
p
r
i
o
r
i
t
y
_
f
n
(
e
l
e
m
 
e
1
,
 
e
l
e
m
 
e
2
)
;
// typedef ______* pq_t;
bool
 
pq_empty
(
pq_t
 
Q
)
  /*@requires Q != NULL;
 
@*/
 ;
pq_t 
pq_new
(
has_higher_priority_fn*
 prio
)
  /*@requires prio != NULL; @*/
  /*@ensures \result != NULL &&  pq_empty(\result);
 
@*/
 ;
void
 
pq_add
(
pq_t
 
Q
, 
elem 
e
)
  /*@requires Q != NULL && e != NULL;
 
@*/
  /*@ensures !pq_empty(Q);
 
@*/
 ;
elem 
pq_rem 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
 
  /*@ensures \result != NULL;
 
@*/
 ;
elem 
pq_peek 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
  /*@ensures \result != NULL && !pq_empty(Q);
 
@*/
 ;
P
r
i
o
r
i
t
y
 
Q
u
e
u
e
 
I
n
t
e
r
f
a
c
e
44
The Bounded Priority Queue Interface
 
pq_new
 now takes the
capacity of the priority queue
 
We need a new function to
check if it is full
o
pq_full
 
We cannot insert an element
into a full priority queue
 
A priority queue is not full
after removing an element
typedef 
void* elem
;
          // Decided by client
t
y
p
e
d
e
f
 
b
o
o
l
 
h
a
s
_
h
i
g
h
e
r
_
p
r
i
o
r
i
t
y
_
f
n
(
e
l
e
m
 
e
1
,
 
e
l
e
m
 
e
2
)
;
// typedef ______* pq_t;
bool
 
pq_empty
(
pq_t
 
Q
)
  /*@requires Q != NULL;
 
@*/
 ;
bool
 
pq_full
(
pq_t
 
Q
)
  /*@requires Q != NULL;
 
@*/
 ;
pq_t 
pq_new
(
int
 
capacity
, 
has_higher_priority_fn*
 prio
)
  /*@requires capacity > 0 && prio != NULL; @*/
  /*@ensures \result != NULL &&  pq_empty(\result);
 
@*/
 ;
void
 
pq_add
(
pq_t
 
Q
, 
elem 
e
)
  /*@requires Q != NULL && !pq_full(Q) && e != NULL;
 
@*/
  /*@ensures !pq_empty(Q);
 
@*/
 ;
elem 
pq_rem 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
 
  /*@ensures \result != NULL && !pq_full(Q);
 
@*/
 ;
elem 
pq_peek 
(
pq_t 
Q
)
  /*@requires Q != NULL && !pq_empty(Q);
 
@*/
  /*@ensures \result != NULL && !pq_empty(Q);
 
@*/
 ;
B
o
u
n
d
e
d
 
P
r
i
o
r
i
t
y
 
Q
u
e
u
e
 
I
n
t
e
r
f
a
c
e
45
Concrete Type
 
The heap data structure needs to store
o
the array that contains the heap elements
o
its true size
that’s capacity + 1
o
the position where to add the next element
o
the priority function
typedef struct 
heap_header heap
;
struct
 
heap_header 
{
  
int
 limit;
 
  
elem[] 
data;
 
// \length(data) == limit
  
int
 next;
 
// 1 <= next  && next <= limit
 
has_higher_priority_fn*
 
prior;
 
 
// != NULL
};
because we sacrifice index 0
46
typedef struct 
heap_header heap
;
struct
 
heap_header 
{
  
int
 limit;
 
// == capacity + 1
  
elem[] 
data;
 
// \length(data) == limit
  
int
 next;
 
// 1 <= next  && next <= limit
 
has_higher_priority_fn*
 
prior;
 
 
// != NULL
};
 
Basic Representation Invariants
 
We simply translate the field constraints
typedef struct 
heap_header heap
;
struct
 
heap_header 
{
  
int
 limit;
  
elem[] 
data;
 
// \length(data) == limit
  
int
 next;
 
// 1 <= next  && next <= limit
 
has_higher_priority_fn*
 
prior;
 
 
// != NULL
};
bool 
is_heap_safe
(
heap*
 
H
) {
  return
 1 < H->limit && H->limit < int_max()/2
       && is_array_expected_length(H->data, H->limit)
       && 1 <= H->next && H->next <= H->limit
       && H->prior != NULL;
}
 
47
Slide Note
Embed
Share

Explore the fundamentals of priority queues, including how they prioritize elements based on specific criteria, such as emergencies or deadlines. Learn about key operations like adding and retrieving elements, with examples from different real-world scenarios. Delve into creating a Priority Queue Interface to enhance functionality and efficiency in managing tasks.

  • Priority Queues
  • Data Structures
  • Imperative Computation
  • Algorithms
  • Programming

Uploaded on Apr 05, 2024 | 2 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript


  1. 15-122: Principles of Imperative Computation Lecture 24: Priority Queues April 17, 2023

  2. Today Last lecture: Graph Search: DFS and BFS Today s lecture: Priority queues: heaps, adding to heaps, removing from heaps, and representing heaps Announcements: Last written assignment is due today by 9PM Last programming assignment is due tomorrow by 9PM (you can use 2 extra grace days for this assignment) The final exam is on Sunday, April 30 from 8:30AM to 11:30AM in Room 2163 1

  3. Review Work lists: Data structures that o Store elements and o Give them back one at a time in some order Stacks: Retrieve the element that was inserted most recently Queues: Retrieve the element that has been there longest Priorityqueues: Retrieve the most interesting element Today 2

  4. The Work List Interface Recall the work list interface template: Now, fully generic Work List Interface typedef void* elem; // Decided by client // typedef ______* wl_t; bool wl_empty(wl_t W) /*@requires W != NULL; @*/ ; wl_t wl_new() /*@ensures \result != NULL && wl_empty(\result); @*/ ; void wl_add(wl_t W, elem e) /*@requires W != NULL && e != NULL; /*@ensures !wl_empty(W); @*/ @*/ ; elem wl_retrieve(wl_t W) /*@requires W != NULL && !wl_empty(W); /*@requires \result != NULL; This is not the interface of an actual data structure but a general template for the work lists we are studying @*/ @*/ ; 3

  5. Priority Queues 4

  6. Priority Queues Retrieve the most interesting element o Elements are given priorities o Retrieve the element with the highest priority o Several elements may have the same priority Examples: o Emergency room Highest priority = most severe condition o Processes in an OS Highest priority = well, it s complicated o Homework due Highest priority = 5

  7. Towards a Priority Queue Interface It will be convenient to have a peek function o It returns the highest priority element without removing it Priority Queue Interface This is the work list interface with names changed typedef void* elem; // Decided by client // typedef ______* pq_t; bool pq_empty(pq_t Q) /*@requires Q != NULL; @*/ ; pq_t pq_new() /*@ensures \result != NULL && pq_empty(\result); @*/ ; void pq_add(pq_t Q, elem e) /*@requires Q != NULL && e != NULL; /*@ensures !pq_empty(Q); @*/ @*/ ; elem pq_rem (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL; @*/ @*/ ; Added elem pq_peek (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL && !pq_empty(Q); @*/ @*/ ; 6

  8. How to Specify Priorities? 1. Mention it as part of pq_add void pq_add(pq_t Q, elem e, int priority) o How do we assign a priority to an element? The same element should always be given the same priority Priorities should form some kind of order o Do bigger numbers represent higher or lower priorities? People are bad at being consistent Potential for lots of errors 7

  9. How to Specify Priorities? 2. Make the priority part of an elem o And provide a way to retrieve it int get_priority(elem e) o How do we assign a priority to an element? The same element should always be given the same priority Priorities should form some kind of order o Do bigger numbers represent higher or lower priorities? Same issues as (1) as (1) Same issues The problem is that assigning a priority to an element is hard for people But given two elements, saying which one has higher priority is easier 8

  10. How to Specify Priorities? 3. Have a way to tell which of two elements has higher priority Given two elements, saying which one has higher priority is easier bool has_higher_priority(elem e1, elem e2) o It returns true if e1 has strictly higher priority than e2 o It is the client who should provide this function Only they know what elem is o For the priority queue library to be generic, we turn it into a type definition typedef bool has_higher_priority_fn(elem e1, elem e2); and have pq_new take a priority function as input 9

  11. The Priority Queue Interface f(e1, e2) returns true if e1 has strictly higher priority than e2 Priority Queue Interface typedef void* elem; // Decided by client typedef bool has_higher_priority_fn(elem e1, elem e2); // typedef ______* pq_t; bool pq_empty(pq_t Q) /*@requires Q != NULL; We commit to the priority function when creating the queue @*/ ; pq_t pq_new(has_higher_priority_fn* prio) /*@requires prio != NULL; @*/ /*@ensures \result != NULL && pq_empty(\result); @*/ ; void pq_add(pq_t Q, elem e) /*@requires Q != NULL && e != NULL; /*@ensures !pq_empty(Q); @*/ @*/ ; elem pq_rem (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL; @*/ @*/ ; elem pq_peek (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL && !pq_empty(Q); @*/ @*/ ; 10

  12. Priority Queue Implementations Unsorted array/list Sorted array/list AVL trees Heaps O(1) O(n) O(log n) O(log n) add O(n) O(1) O(log n) O(log n) rem O(n) O(1) O(log n) O(1) peek Cost of add using arrays are amortized 11

  13. Heaps 12

  14. Nothing to do with the memory segment Heaps A heap is a type of binary tree used to implement priority queues Since add and rem have cost O(log n), a heap is a balanced binary tree o In fact, they are as balanced as a tree can be Since peek has cost O(1), the highest priority element must be at the root o In fact, the elements on any path from a leaf to the root are ordered in increasing priority order highest priority lower priority 13

  15. Heaps Invariants 1. Shape invariant 2. Ordering invariant o The priority of a child is lower than or equal to the priority of its parent or equivalently o The priority of a parent is higher than or equal to the priority of its children higher priority Point of view of child Point of view of parent Both points of view will come handy 14

  16. The Many Things Called Heaps A heap is a type of binary tree used to implement priority queues A heap is also any priority queue where priorities are integers o It is a min-heap if smaller numbers represent higher priorities o It is a max-heap if bigger numbers represent higher priorities A heap is the segment of memory we called allocated memory This is a significant source of confusion 15

  17. Min-heaps Any priority queue where priorities are integers and smaller numbers represent higher priorities In practice, most priority queues are implemented as min-heaps o And heap is also shorthand for min-heap more confusion! Most of our examples will be min-heaps 1. Shape invariant 2. Ordering invariant The valueof a child is the value of its parent or equivalently The valueof a parent is the value of its children larger value 16

  18. Activity Draw a min-heap with values 1, 2, 2, 9, 7 17

  19. Activity Draw a min-heap with values 1, 2, 2, 9, 7 1 1 2 2 2 2 7 9 9 7 1 1 2 9 2 7 2 7 9 2 and several more 18

  20. Insertion into a Heap 19

  21. Insertion Strategy Maintain the shape invariant larger value Temporary break and then restore the ordering invariant Min-heap version This is similar to what we did for AVL trees Maintain the ordering invariant Temporary break and then restore the height invariant 20

  22. Example We start by putting the new element in the only place that maintains the shape invariant o But doing so may break the ordering invariant 2 2 Insert 1 4 7 4 7 9 4 8 9 4 8 1 This is a min-heap 1 must go here This violates the ordering invariant o How to fix it? 21

  23. Swapping Up How to fix the violation? o Swap the child with the parent We swapped 7 and 1 2 2 Swap up 4 7 4 1 9 4 8 1 9 4 8 7 o Swapping up may introduce a new violation This introduced a new violation of the ordering invariant one level up 22

  24. Swapping Up How to fix the violation? o Swap the child with the parent We swapped 2 and 1 2 1 Swap up 4 1 4 2 9 4 8 7 9 4 8 7 We stop when no new violation is introduced o Or we reach the root There are no more violations. This is a valid min-heap 23

  25. Adding an Element General procedure 1. Put the added element in the one place that maintains the shape invariant The leftmost open slot on the last level Or, if the last level is full, the leftmost slot on the next level 2. Repeatedly swap it up with its parent Until the violation is fixed Or we reach the root o There is always at most one violation The overall process is called sifting up For a heap with n elements This costs O(log n) o Because we make at most O(log n) swaps 24

  26. Removing the Minimal Element of a Heap 25

  27. Deletion Strategy Maintain the shape invariant larger value Temporary break and then restore the ordering invariant Min-heap version Same as insertion 26

  28. Example We must return the root And replace it with the only element that maintains the shape invariant 1 9 Rem 4 2 4 2 7 4 8 9 7 4 8 This causes This causes two violations two violations We must return 1 We replace it with 9 Which violation to fix first? 27

  29. Swapping Down Which violation to fix first? o If we swap 4 and 9, we end up with three violations 9 4 Swap down 4 2 9 2 7 4 8 7 4 8 Can we do better? 28

  30. Swapping Down If we swap 9 and 2, we end up with one violation o At most two in general 9 2 Swap down 4 2 4 9 7 4 8 7 4 8 When swapping down, always swap with the child with the highest priority o Smallest value in a min-heap 29

  31. Swapping Down Always swap the child with the highest priority 2 2 Swap down 4 9 4 8 7 4 8 7 4 9 We stop when no new violations are introduced o Or we reach a leaf 30

  32. Removing an Element General procedure 1. Return the root 2. Replace it with the element in the one place that maintains the shape invariant The rightmost element on the last level 3. Repeatedly swap it down with its child that has highest priority Until all violations are fixed Or we reach a leaf o This guarantees there are always at most two violations The overall process is called sifting down For a heap with n elements This costs O(log n) o Because we make at most O(log n) swaps 31

  33. Priority Queue Implementations Unsorted array/list Sorted array/list AVL trees Heaps O(1) O(n) O(log n) O(log n) add O(n) O(1) O(log n) O(log n) rem O(n) O(1) O(log n) O(1) peek Cost of add using arrays are amortized 32

  34. Representing Heaps 33

  35. How to Represent a Heap? Borrowing from BSTs, we could use pointers o left child and right child Needed when sifting down o parent node Needed when sifting up 2 typedef struct heap_node heap; struct heap_node { elem data; heap* parent; heap* left; heap* right; }; 4 7 4 That s a lot of pointers to keep track of! o It also takes up a lot of space Try writing the swap function! Can we do better? 34

  36. Understanding Heaps Let s number the nodes level by level starting at 1 1 2 2 3 4 8 4 5 6 7 4 9 Observations: o If a node has number i, its left child has number o If a node has number i, its right child has number o If a node has number i, its parent has number 2i 2i + 1 i/2 35

  37. Understanding Heaps 1 2 2 3 4 8 4 5 6 7 4 9 o If a node has number i, its left child has number o If a node has number i, its right child has number 2i + 1 o If a node has number i, its parent has number 2i i/2 By numbering nodes this way, we can navigate the tree up and down using arithmetic 36

  38. Understanding Heaps 1 2 2 3 4 8 4 5 6 7 4 9 By numbering nodes this way, we can navigate the tree up and down using arithmetic These numbers are contiguous and start at 1 37

  39. Understanding Heaps 1 2 2 3 4 8 4 5 6 7 4 9 These numbers are contiguous and start at 1 Do we know of any data structure that allows accessing data based on consecutive integers? Arrays! 38

  40. Representing Heaps using Arrays 1 2 2 3 4 8 4 5 6 7 4 9 0 1 2 3 4 5 6 2 4 8 7 4 9 For simplicity, we do not use index 0 If a node has number i, its left child has number If a node has number i, its right child has number 2i + 1 if a node has number i, its parent has number 2i i/2 39

  41. Representing Heaps using Arrays add will initially put a new element at index 7 1 2 2 3 4 8 4 5 6 7 4 9 0 1 2 3 4 5 6 2 4 8 7 4 9 40

  42. Representing Heaps using Arrays add will initially put a new element at index 7 remove will yank the element at index 6 1 2 2 3 4 8 4 5 6 7 4 9 We are better off having unused positions 0 1 2 3 4 5 6 7 8 9 2 4 8 7 4 9 41

  43. Bounded Priority Queues 43

  44. Types of Work Lists Priority Queue Interface The work lists we considered so far were unbounded o There was no maximum to the number of elements they could hold typedef void* elem; // Decided by client typedef bool has_higher_priority_fn(elem e1, elem e2); // typedef ______* pq_t; bool pq_empty(pq_t Q) /*@requires Q != NULL; @*/ ; pq_t pq_new(has_higher_priority_fn* prio) /*@requires prio != NULL; @*/ /*@ensures \result != NULL && pq_empty(\result); @*/ ; A bounded work list has a capacity fixed at creation time o We can t add elements once full void pq_add(pq_t Q, elem e) /*@requires Q != NULL && e != NULL; /*@ensures !pq_empty(Q); @*/ @*/ ; elem pq_rem (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL; @*/ @*/ ; In practice o Stacks are typically unbounded o Queues can be either o Priority queues are often bounded elem pq_peek (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL && !pq_empty(Q); @*/ @*/ ; 44

  45. The Bounded Priority Queue Interface pq_new now takes the capacity of the priority queue Bounded Priority Queue Interface typedef void* elem; // Decided by client typedef bool has_higher_priority_fn(elem e1, elem e2); // typedef ______* pq_t; We need a new function to check if it is full o pq_full bool pq_empty(pq_t Q) /*@requires Q != NULL; @*/ ; bool pq_full(pq_t Q) /*@requires Q != NULL; @*/ ; pq_t pq_new(int capacity, has_higher_priority_fn* prio) /*@requires capacity > 0 && prio != NULL; @*/ /*@ensures \result != NULL && pq_empty(\result); We cannot insert an element into a full priority queue @*/ ; void pq_add(pq_t Q, elem e) /*@requires Q != NULL && !pq_full(Q) && e != NULL; @*/ /*@ensures !pq_empty(Q); @*/ ; A priority queue is not full after removing an element elem pq_rem (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL && !pq_full(Q); @*/ @*/ ; elem pq_peek (pq_t Q) /*@requires Q != NULL && !pq_empty(Q); /*@ensures \result != NULL && !pq_empty(Q); @*/ @*/ ; 45

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#