程序代写代做代考 algorithm data structure C COMP 250

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 cur.left.key) || (cur.right!=null && cur.key > cur.right.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