D ATA S TRUCTURES II
‣ binary heap demo
Lecture slides by Kevin Wayne
h t t p : / / w w w . c s . p r i n c e t o n . e d u / ~w a y ne / k l e i nb e r g - t a r d o s
Abdur Rashid Tushar
Lecturer, CSE, BUET
Last updated on 27.07.23 07:11
Binary heap demo
heap ordered
1
8
0
1 1 1 2
2 8 1 5
2 1 1
1 7 9
2
Binary heap demo
Insert. Add node at end; repeatedly exchange element in child with element
in parent until heap order is restored.
insert 7
1
8
0
1 1 1 2
2 8 1 5
2 1 1
7 add to heap
1 7 9
3
Binary heap demo
Insert. Add node at end; repeatedly exchange element in child with element
in parent until heap order is restored.
insert 7
1
8
0
1 1 1 2
2 8 1 5
2 1 1 violates heap order
7
1 7 9 (swim up)
4
Binary heap demo
Insert. Add node at end; repeatedly exchange element in child with element
in parent until heap order is restored.
insert 7
1
8
0
1 1 2
7
2 1 5
2 1 1 1 violates heap order
1 7 9 8 (swim up)
5
Binary heap demo
Insert. Add node at end; repeatedly exchange element in child with element
in parent until heap order is restored.
insert 7
7 8
1 1 1 2
2 0 1 5
2 1 1 1 violates heap order
1 7 9 8 (swim up)
6
Binary heap demo
heap ordered
7 8
1 1 1 2
2 0 1 5
2 1 1 1
1 7 9 8
7
Binary heap demo
Extract min. Exchange root node with last node; repeatedly exchange
element in parent with element in larger child until heap order is restored.
extract the minimum
7 8
1 1 1 2
2 0 1 5
2 1 1 1
1 7 9 8
8
Binary heap demo
Extract min. Exchange root node with last node; repeatedly exchange
element in parent with element in larger child until heap order is restored.
extract the minimum
7 8
1 1 1 2
2 0 1 5
2 1 1 1
1 7 9 8 exchange with root
9
Binary heap demo
Extract min. Exchange root node with last node; repeatedly exchange
element in parent with element in larger child until heap order is restored.
extract the minimum
1
8
7 8
1 1 1 2
2 0 1 5
2 1 1
6 exchange with root
1 7 9
10
Binary heap demo
Extract min. Exchange root node with last node; repeatedly exchange
element in parent with element in larger child until heap order is restored.
extract the minimum
violates heap order
1
8 (sink down)
7 8
1 1 1 2
2 0 1 5
2 1 1
6
1 7 9
11
Binary heap demo
Extract min. Exchange root node with last node; repeatedly exchange
element in parent with element in larger child until heap order is restored.
extract the minimum
violates heap order
7 (sink down)
1
8
8
1 1 1 2
2 0 1 5
2 1 1
6
1 7 9
12
Binary heap demo
Extract min. Exchange root node with last node; repeatedly exchange
element in parent with element in larger child until heap order is restored.
extract the minimum
violates heap order
7 (sink down)
1
8
0
1 1 1 2
2 8 1 5
2 1 1
6
1 7 9
13
Binary heap demo
heap ordered
1
8
0
1 1 1 2
2 8 1 5
2 1 1
1 7 9
14
