Heaps: A Fundamental Data Structure in Programming
Topic 24
Heaps
"
Y
o
u
t
h
i
n
k
y
o
u
k
n
o
w
w
h
e
n
y
o
u
c
a
n
l
e
a
r
n
,
a
r
e
m
o
r
e
s
u
r
e
w
h
e
n
y
o
u
c
a
n
w
r
i
t
e
,
e
v
e
n
m
o
r
e
w
h
e
n
y
o
u
c
a
n
t
e
a
c
h
,
b
u
t
c
e
r
t
a
i
n
w
h
e
n
y
o
u
c
a
n
p
r
o
g
r
a
m
.
"
- Alan Perlis
Priority Queue
8
Recall priority queue
–
elements enqueued based on priority
–
dequeue removes the highest priority item
8
Options?
–
List? Binary Search Tree?
Clicker 1
Linked List enqueue
BST enqueue
A.
O(N)
O(1)
B.
O(N)
O(logN)
C.
O(N)
O(N)
D.
O(logN)
O(logN)
E.
O(1)
O(logN)
CS314
Heaps
2
Another Option
8
The
heap
data structure
–
not to be confused with the runtime heap (portion
of memory for dynamically allocated variables)
8
Typically a complete binary tree (variations
with more than 2 children possible)
–
all levels have maximum number of nodes
except deepest where nodes are filled in from
left to right
8
Maintains the
heap order property
–
in a min heap the value in the root of any subtree
is less than or equal to all other values in the
subtree
CS314
Heaps
3
Clicker 2
8
In a max heap with no duplicates where is
the largest value?
A.
the root of the tree
B.
in the left-most node
C.
in the right-most node
D.
a node in the lowest level
E.
none of these
CS314
Heaps
4
Example Min Heap
CS314
Heaps
5
1
2
1
7
1
5
1
9
5
2
3
7
2
5
4
5
2
1
Add Operation
8
Add new element to next open spot in array
8
Swap with parent if new value is less
than parent
8
Continue back up the tree as long as the
new value is less than new parent node
CS314
Heaps
6
Add Example
8
Add 15 to heap (initially next left most node)
CS314
Heaps
7
1
2
1
7
1
5
1
9
5
2
3
7
2
5
4
5
2
1
1
5
Add Example
8
Swap 15 and 52
CS314
Heaps
8
1
2
1
7
1
5
1
9
1
5
3
7
2
5
4
5
2
1
5
2
Enqueue Example
8
Swap 15 and 17, then stop
CS314
Heaps
9
1
2
1
5
1
5
1
9
1
7
3
7
2
5
4
5
2
1
5
2
Add Example
8
Insert the following values 1 at a time into a
min heap:
16 9 5 8 13 8 8 5 5 19 27 9 3
CS314
Heaps
10
10
Internal Storage
8
Interestingly heaps are often implemented
with an array instead of nodes
CS314
Heaps
11
11
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
1
7
1
5
1
9
5
2
3
7
2
5
4
5
2
1
for element at index i:
parent index:
i / 2
left child index:
i * 2
right child index:
i * 2 + 1
CS314
Heaps
12
12
I
n
H
o
n
o
r
o
f
E
l
i
j
a
h
,
T
h
e
M
e
m
e
K
i
n
g
,
S
p
r
i
n
g
2
0
2
0
PriorityQueue Class
CS314
Heaps
13
13
public class PriorityQueue<E extends Comparable<? super E>>
{private int size;
private E[] con;
public PriorityQueue() {con = getArray(2);
}
private E[] getArray(int size) {return (E[]) (new Comparable[size]);
}
PriorityQueue enqueue / add
14
14
public void enqueue(E val) {if ( size >= con.length - 1 )
enlargeArray(con.length * 2);
size++;
int indexToPlace = size;
while ( indexToPlace > 1
&& val.compareTo( con[indexToPlace / 2] ) < 0 ) {con[indexToPlace] = con[indexToPlace / 2]; // swap
indexToPlace /= 2; // change indexToPlace to parent
}
con[indexToPlace] = val;
}
private void enlargeArray(int newSize) {E[] temp = getArray(newSize);
System.
arraycopy(con, 1, temp, 1, size);
con = temp;
}
Enqueue / add Example
With Array Shown
8
Add 15 to heap
(initially next
left most node)
1
2
1
7
1
5
1
9
5
2
3
7
2
5
4
5
2
1
1
5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
1
7
1
5
1
9
5
2
3
7
2
5
4
5
2
1
1
5
1
0
/
2
=
5
(
i
n
d
e
x
o
f
p
a
r
e
n
t
)
Enqueue Example
With Array Shown
8
Swap 15 and 52
1
2
1
7
1
5
1
9
1
5
3
7
2
5
4
5
2
1
5
2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
1
7
1
5
1
9
1
5
3
7
2
5
4
5
2
1
5
2
5
/
2
=
2
(
i
n
d
e
x
o
f
p
a
r
e
n
t
)
Enqueue Example
With Array Shown
8
Swap 15 and 17
1
2
1
7
1
5
1
9
1
5
3
7
2
5
4
5
2
1
5
2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
1
5
1
5
1
9
1
7
3
7
2
5
4
5
2
1
5
2
2
/
2
=
1
(
i
n
d
e
x
o
f
p
a
r
e
n
t
)
Enqueue Example
With Array Shown
8
15 !< 12 -> DONE
1
2
1
7
1
5
1
9
1
5
3
7
2
5
4
5
2
1
5
2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
1
5
1
6
1
9
1
7
3
7
2
5
4
5
2
1
5
2
2
/
1
=
1
(
i
n
d
e
x
o
f
p
a
r
e
n
t
)
8
Remove -> remove 12
CS314
Heaps
19
19
1
2
1
7
1
5
1
9
1
5
3
7
2
5
4
5
2
1
5
2
Remove / Dequeue
8
min value / front of queue is in root of tree
8
swap value from last node to root and move
down swapping with smaller child unless
values is smaller than both children
CS314
Heaps
20
20
Dequeue Example
8
Swap 35
into root
(save 12
to return)
1
2
1
5
1
3
1
7
2
3
4
5
5
3
4
5
2
1
3
5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
1
5
1
3
1
7
2
3
4
5
5
3
4
5
2
1
3
5
Dequeue Example
8
Swap 35
into root
(save 12
to return)
3
5
1
5
1
3
1
7
2
3
4
5
5
3
4
5
2
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3
5
1
5
1
3
1
7
2
3
4
5
5
3
4
5
2
1
Dequeue Example
8
Min child?
8
1 * 2 = 2 -> 15
8
1 * 2 + 1 = 3 -> 13
8
Swap with 13
3
5
1
5
1
3
1
7
2
3
4
5
5
3
4
5
2
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3
5
1
5
1
3
1
7
2
3
4
5
5
3
4
5
2
1
Dequeue Example
1
3
1
5
3
5
1
7
2
3
4
5
5
3
4
5
2
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
3
1
5
3
5
1
7
2
3
4
5
5
3
4
5
2
1
Dequeue Example
1
3
1
5
3
5
1
7
2
3
4
5
5
3
4
5
2
1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
3
1
5
3
5
1
7
2
3
4
5
5
3
4
5
2
1
8
Min child?
8
3 * 2 = 6 -> 45
8
3 * 2 + 1 = 7 -> 53
8
Less than or equal to
both of my children!
Stop!
Dequeue Code
26
26
public E dequeue( ) {E top = con[1];
int hole = 1;
boolean done = false;
while ( hole * 2 < size && ! done ) {int child = hole * 2;
// see which child is smaller
if ( con[child].compareTo( con[child + 1] ) > 0 )
child++; // child now points to smaller
// is replacement value bigger than child?
if (con[size].compareTo( con[child] ) > 0 ) {con[hole] = con[child];
hole = child;
}
else
done = true;
}
con[hole] = con[size];
size--;
return top;
}
Clicker 3
- PriorityQueue Comparison
8
Run a Stress test of PQ implemented with
Heap and PQ implemented with
BinarySearchTree
8
What will result be?
A.
Heap takes half the time or less of BST
B.
Heap faster, but not twice as fast
C.
About the same
D.
BST faster, but not twice as fast
E.
BST takes half the time or less of Heap
CS314
Heaps
27
27
Alan Perlis' quote emphasizes the certainty that comes with programming, showcasing the progression from learning to teaching. The concept of heaps, a type of binary tree data structure, is explored in this material. Heaps maintain a hierarchical order, with the root of the tree containing the minimum or maximum value. Various operations like enqueue and add are illustrated through examples, highlighting the structure and functionality of heaps.
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
Topic 24 Heaps "You think you know when you can learn, are more sure when you can write, even more when you can teach, but certain when you can program." - Alan Perlis
Priority Queue Recall priority queue elements enqueued based on priority dequeue removes the highest priority item Options? List? Binary Search Tree? Clicker 1 Linked List enqueue A. O(N) B. O(N) C. O(N) D. O(logN) E. O(1) BST enqueue O(1) O(logN) O(N) O(logN) O(logN) CS314 Heaps 2
Another Option The heap data structure not to be confused with the runtime heap (portion of memory for dynamically allocated variables) Typically a complete binary tree (variations with more than 2 children possible) all levels have maximum number of nodes except deepest where nodes are filled in from left to right Maintains the heap order property in a min heap the value in the root of any subtree is less than or equal to all other values in the subtree CS314 Heaps 3
Clicker 2 In a max heap with no duplicates where is the largest value? A. the root of the tree B. in the left-most node C. in the right-most node D. a node in the lowest level E. none of these CS314 Heaps 4
Example Min Heap 12 17 15 19 37 52 25 45 21 CS314 Heaps 5
Add Operation Add new element to next open spot in array Swap with parent if new value is less than parent Continue back up the tree as long as the new value is less than new parent node CS314 Heaps 6
Add Example Add 15 to heap (initially next left most node) 12 17 15 19 37 52 25 45 21 15 CS314 Heaps 7
Add Example Swap 15 and 52 12 17 15 19 37 15 25 45 21 52 CS314 Heaps 8
Enqueue Example Swap 15 and 17, then stop 12 15 15 19 37 17 25 45 21 52 CS314 Heaps 9
Add Example Insert the following values 1 at a time into a min heap: 16 9 5 8 13 8 8 5 5 19 27 9 3 CS314 Heaps 10
Internal Storage Interestingly heaps are often implemented with an array instead of nodes for element at index i: parent index: i / 2 left child index: i * 2 right child index: i * 2 + 1 12 17 15 19 37 52 25 45 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12 17 15 19 52 37 25 45 21 CS314 Heaps 11
In Honor of Elijah, The Meme King, Spring 2020 CS314 Heaps 12
PriorityQueue Class public class PriorityQueue<E extends Comparable<? super E>> { private int size; private E[] con; public PriorityQueue() { con = getArray(2); } private E[] getArray(int size) { return (E[]) (new Comparable[size]); } CS314 Heaps 13
PriorityQueue enqueue / add public void enqueue(E val) { if ( size >= con.length - 1 ) enlargeArray(con.length * 2); size++; int indexToPlace = size; while ( indexToPlace > 1 && val.compareTo( con[indexToPlace / 2] ) < 0 ) { con[indexToPlace] = con[indexToPlace / 2]; // swap indexToPlace /= 2; // change indexToPlace to parent } con[indexToPlace] = val; } private void enlargeArray(int newSize) { E[] temp = getArray(newSize); System.arraycopy(con, 1, temp, 1, size); con = temp; } 14
Enqueue / add Example With Array Shown Add 15 to heap (initially next left most node) 12 17 15 19 37 52 25 45 21 15 10 / 2 = 5 (index of parent) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12 17 15 19 52 37 25 45 2115
Enqueue Example With Array Shown Swap 15 and 52 12 17 15 19 37 15 25 45 21 52 5 / 2 = 2 (index of parent) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12 17 15 19 15 37 25 45 21 52
Enqueue Example With Array Shown Swap 15 and 17 12 15 15 19 37 25 17 45 21 52 2 / 2 = 1 (index of parent) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12 15 15 19 17 37 25 45 21 52
Enqueue Example With Array Shown 15 !< 12 -> DONE 12 15 15 19 37 25 17 45 21 52 2 / 1 = 1 (index of parent) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12 15 16 19 17 37 25 45 21 52
Remove -> remove 12 12 15 15 19 37 25 17 45 21 52 CS314 Heaps 19
Remove / Dequeue min value / front of queue is in root of tree swap value from last node to root and move down swapping with smaller child unless values is smaller than both children CS314 Heaps 20
Dequeue Example Swap 35 into root (save 12 to return) 15 12 13 17 45 23 53 45 21 35 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 12 15 13 17 23 45 53 45 21 35
Dequeue Example Swap 35 into root (save 12 to return) 15 35 13 17 45 23 53 45 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 35 15 13 17 23 45 53 45 21
Dequeue Example Min child? 1 * 2 = 2 -> 15 1 * 2 + 1 = 3 -> 13 Swap with 13 35 15 13 17 45 23 53 45 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 35 15 13 17 23 45 53 45 21
Dequeue Example 13 15 35 17 45 23 53 45 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 13 15 35 17 23 45 53 45 21
Dequeue Example Min child? 3 * 2 = 6 -> 45 3 * 2 + 1 = 7 -> 53 Less than or equal to both of my children! Stop! 13 15 35 17 45 23 53 45 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 13 15 35 17 23 45 53 45 21
Dequeue Code public E dequeue( ) { E top = con[1]; int hole = 1; boolean done = false; while ( hole * 2 < size && ! done ) { int child = hole * 2; // see which child is smaller if ( con[child].compareTo( con[child + 1] ) > 0 ) child++; // child now points to smaller // is replacement value bigger than child? if (con[size].compareTo( con[child] ) > 0 ) { con[hole] = con[child]; hole = child; } else done = true; } con[hole] = con[size]; size--; return top; } 26
Clicker 3 - PriorityQueue Comparison Run a Stress test of PQ implemented with Heap and PQ implemented with BinarySearchTree What will result be? A. Heap takes half the time or less of BST B. Heap faster, but not twice as fast C. About the same D. BST faster, but not twice as fast E. BST takes half the time or less of Heap CS314 Heaps 27
