COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 12-2 : Heaps
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Heaps
HEAPS
PRIORITY QUEUE
Assume a set of comparable elements or “keys”.
Like a queue, but now we have a more general definition of which element to remove next, namely the one with highest priority.
e.g. hospital emergency room
PRIORITYQUEUE ADT
add(key)
removeMin()
“highest” priority = “number 1” priority
peek()
contains(element) remove(element)
HOW TO IMPLEMENT A PRIORITY QUEUE ?
sorted list ?
binary search tree (last lecture) ?
balanced binary search tree (COMP 251) ? heap (next 2 lectures)
Not the same “heap” you hear about in COMP 206.
COMPLETE BINARY TREE (DEFINITION)
f
c ae
dd
Binary tree of height h such that every level less than h is full, and all nodes at level h are as far to the left as possible
MIN HEAP (DEFINITION)
a
e fluk
m
b
Complete binary tree with unique comparable elements, such that each node’s element (key) is less than its children’s element (key).
ADD()
For example,
add(c)
a
b
e fluk
m
ADD()
For example,
add(c)
a
b fluk
?
e
m
ADD()
For example,
add(c)
a
What can we do?
e
b
m
fluk
c
Problem : adding at the next available slot typically destroys the heap property.
ADD()
For example,
add(c) a
b
cluk f
What can we do?
Let’s swap c with its parent f.
e
Q: Can this create a problem with c’s former sibling, who is now c’s child?
m
ADD()
For example,
add(c) a
b
cluk f
What can we do?
Let’s swap c with its parent f.
e
Q: Can this create a problem with c’s former sibling, who is now c’s child?
A: No. Why?
m
ADD()
For example,
add(c) a
b
cluk f
Q: Are we done?
A: Not necessarily. What about c’s parent?
e
m
ADD()
For example,
add(c) a
b
eluk f
We swap c with its (new) parent e.
Now we are done because c is greater than its parent a
c
m
ADD() – IMPLEMENTATION
a
b
eluk f
add(key) {
cur = new node at next available leaf position cur.key = key
}
c
m
ADD() – IMPLEMENTATION
a
b
eluk f
add(key){
cur = new node at next available leaf position cur.key = key
if(root == null) // empty tree
}
root = cur
c
m
ADD() – IMPLEMENTATION
a
b
eluk f
add(key){
cur = new node at next available leaf position cur.key = key
if(root == null) // empty tree
root = cur
else {
while (cur!=root && cur.key
}
return temp }
c
m
REMOVEMIN() – IMPLEMENTATION
a
b
eluk f
removeMin(){
temp = root.key
remove the last leaf node and
store its key into the root
cur = root
while((cur.left!=null && cur.key > cur.left.key) || (cur.right!=null && cur.key > cur.right.key)) {
minChild = child with smaller key
swapKeys(cur, minChild)
cur = minChild
}
return temp }
c
m
add() removeMin()
“upHeap” “downHeap”
REMOVE()
Q: What about remove(key) ?
REMOVE()
Q: What about remove(key) ? A: Worst case 𝑂 𝑛
HEAP (ARRAYIMPLEMENTATION)
1 2c3
f
Not used
4a5e6 7 d d d d d
8 9 10 11 12 13
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
HEAP (ARRAYIMPLEMENTATION)
1 2e3b
a
4f5l6u7k
z
8 9 10 11 12 13
Not used
m g n
qw
a
e
b
f
l
u
k
m
g
n
q
w
z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
HEAP INDEX RELATIONS
parent = child / 2
left = 2*parent right = 2*parent + 1
1 2e3b
a
4f5l6u7k
z
Not used
m g n
8 9 10 11 12 13
qw
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
HEAP INDEX RELATIONS
parent = child / 2
left = 2*parent right = 2*parent + 1
a
1 2e3b
4f5l6u7k
z
Not used
m g n
8 9 10 11 12 13
qw
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
HEAP INDEX RELATIONS
parent = child / 2
left = 2*parent right = 2*parent + 1
a
1 2e3b
4f5l6u7k
z
Not used
m g n
8 9 10 11 12 13
qw
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
HEAP INDEX RELATIONS
parent = child / 2
left = 2*parent right = 2*parent + 1
a
1 2e3b
4f5l6u7k
z
Not used
m g n
8 9 10 11 12 13
qw
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ASIDE: an array data structure can be used for any binary tree. But this is uncommon and often inefficient.
a
1 2e3b
4f5 6u7k
mg
z
8 9 10 11 12 13
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a
e
b
f
u
k
m
g
z
ADD() – IMPLEMENTATION
add(key){
size = size + 1 // number of elements in heap
// assuming array has room for another element
heap[ size ] = key
i = size
// the following is sometimes called “upHeap”
while ( i > 1 && heap[i] < heap[ i/2 ]){ swapElements( i, i/2 )
i = i/2
} }
E.G. add(c)
1 2e3b
a
4f5l6u7k m
Not used
8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a
e
b
f
l
u
k
m
E.G. add(c)
1 2e3b
a
4f5l6u7k c
Not used
m
89
a
e
b
f
l
u
k
m
c
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
E.G. add(c)
1 2e3b
a
4c5l6u7k f
Not used
m
89
a
e
b
c
l
u
k
m
f
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
E.G. add(c)
1 2c3b
a
4e5l6u7k f
Not used
m
89
a
c
b
e
l
u
k
m
f
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
NEXT VIDEO
write removeMin() using array indices discuss best and worst case
faster algorithm for building a heap
In the next video: More on heaps