CS 112: Data Structures
Sesh Venugopal
Heap – Operations
Heap Structure and Function
From the structural point of view, the heap is a special type of binary tree.
From the functional point of view, it can be used either as a priority queue, which is a specialization of the regular FIFO queue we studied earlier, or as a structure for sorting.
Here we will study in detail the role of the heap as a priority queue.
(We will cover the sorting function later.)
Sesh Venugopal CS 112: Heap Operations 2
Heap as Priority Queue
In the role of a priority queue, the heap acts as a data structure in which the items have different priorities of removal: the item with the highest priority is the one that will be removed next.
A FIFO queue may be considered a special case of a priority queue, in which the priority of an item is the time of its arrival in the queue:
the earlier the arrival time, the higher the priority, which means the item that arrived earliest is at the front of the queue.
Sesh Venugopal CS 112: Heap Operations 3
A heap has two defining properties:
1. Structure: A heap is a complete binary tree, i.e. one in which every level but the last must have the maximum number of nodes possible at that level. The last level may have fewer than the maximum possible nodes, but they should be arranged from left to right without any empty spots.
2. Order: the key at any node x is greater than or equal to the keys at its children
Sesh Venugopal CS 112: Heap Operations 4
Heap Structure
✓
✓✗✓
Sesh Venugopal
CS 112: Heap Operations 5
✓
✗
Heap Order
2 2 5 10
✓
✓
27 87
✗48 ✓
2
Sesh Venugopal
CS 112: Heap Operations
6
Heap Operations
As a priority queue, a heap must provide the same fundamental operations as a FIFO queue.
Specifically, it must provide an insert operation that inserts a new item in the heap—this new item must enter with a specified priority.
Also, it must provide a delete operation that removes the item at the front of the priority queue—this would be the item that has the highest priority of all in the heap, which is the item at the top of the heap.
Sesh Venugopal CS 112: Heap Operations 7
Heap Insert
Inserting a new key in a heap must ensure that after insertion, both the heap structure and the heap order properties are satisfied.
Structure: First, insert the new key so that the heap structure property is satisfied, meaning that the new tree after insertion is also complete.
Insert 20
20 must be inserted as the left child of 8.
This is the only position for a new node that will ensure that the new heap is also a complete binary tree – the last level nodes are arranged left to right without gaps
Sesh Venugopal CS 112: Heap Operations 8
Heap Insert
Inserting a new key in a heap must ensure that after insertion, both the heap structure and the heap order properties are satisfied.
Order: Second, make sure that the heap order property is satisfied by sifting up the newly inserted key.
1. 20 is compared with 8 2. Since it is larger, it is swapped with 8
1 comparison + 1 swap
1. 20 is compared with 15 2. Since it is larger, it is swapped with 15
1 comparison + 1 swap
Total: 2 comparisons + 2 swaps
Sesh Venugopal
CS 112: Heap Operations
9
Heap Insert
Sift Up
Sifting up consists of comparing the new key with its parent, and swapping them if the new key is greater than its parent
In the best case, a comparison
is made but no swap is done – here 10 is inserted but it it is not greater than its parent, 15.
So 1 comparison, no swap
In the worst case, comparisons and swaps are done all the way up to the root:
Sesh Venugopal CS 112: Heap Operations 10
Heap Delete
The item at the top of the heap is the one with the maximum key. Deletion removes this item from the heap. This leaves a vacant spot at the root, and the heap has to be restored so there is no vacant spot.
20 17
12
10
20 is deleted from the top
10 1715 1715
12
15
8 10
12 10
12 8
10
12 12 8 10
The vacant spot is filled in with the item at the “last” node
The last node is deleted
The sequence so far adjusts the heap structure so that there are no vacant spots, and there is one node less. But the heap order has to be restored as well, and this is done by sifting down the item at the top of the heap
Sesh Venugopal CS 112: Heap Operations 11
10
Heap Delete
Sift Down
10
10 17
12 12
The item at the top of the heap is sifted down to restore the heap order
15
8 10
17 17
2
17
8 10
1
15
2
1015 1215
12
12
12 1 12 8
1. The children of 10 are
10
10 12 8 10 The heap is fully restored!
Total: 4 comparisons + 2 swaps
1. The children of 10 are compared to find the larger, which is 17
2 .17 is compared with 10 and since it is larger, it is swapped with 10
2 comparisons + 1 swap
compared to find the larger: it’s a tie, so either of the 12’s can be picked
2 .12 is compared with 10 and since it is larger, it is swapped with 10
2 comparisons + 1 swap
In the example, in the second iteration of sift down, the tie between the 12’s was broken in favor of the left child 12. But we could equally well have broken the tie in favor of the right child 12, in which case, in the final heap, 10 would appear as the right child of the parent 12, instead of the left child
Sesh Venugopal CS 112: Heap Operations 12
Heap Delete – Example 2
17
12 15 12 15 12 15
10 12 8 10
17 is deleted from the top
10 12 8 10
10 from last node is copied over into the top vacant spot
10
10
10 12 8 10
Last node 10 is deleted
10
15 12
12
2
10
8
12115 1215
10
10 12 8
1. 12 and 15 are compared, and 15 being larger is picked 2. 15 is larger than 10, so it is swapped with 10
2 comparisons +1 swap
10 12 8
10 is sifted down from the top
1. 10 has only one child, 8 2. 8 is not larger than 10, so no swap
1 comparison + no swap
Sesh Venugopal
CS 112: Heap Operations
13
Worst case Big O running time
Heap is a complete tree, so all levels except last must be full. Let’s assume that the last level is full as well – it won’t make a difference for the big O result
level 0 level 1
level 2
level h
Assume the height of the heap is h
The number of nodes/items, n, in this heap is computed by adding up the number of nodes at each level, and we can then write h in terms of n:
n
=> n+1=2h+1
=> h + 1 = log2(n+1) => h = log2(n+1) – 1
Sesh Venugopal CS 112: Heap Operations 14
Worst case Big O running time – insert
The actual insertion of a new node is O(1) time.
The restoration of the heap order using sift up is where the real work is done.
level 0 level 1
level 2
Sifting up takes one comparison per level between the new key and its parent.
In the worst case, the new key may be sifted all the way up to the root, or h levels,
for a total of h comparisons. Since h = log2(n+1) – 1, the total number of comparisons is
log2(n+1) – 1 ≡ 𝑂(log 𝑛)
The total time for insert is O(1) + 𝑂(log 𝑛) = 𝑂(log 𝑛)
(We are not counting swaps. Since a swap is only done when a comparison is done,
the number of comparisons is a proxy for swaps as well, and it does not change the big O)
level h
Sesh Venugopal CS 112: Heap Operations 15
Worst case Big O running time – delete
Copying the item in the last node to the top node, and deleting the last node will take O(1) time.
The restoration of the heap order using sift down is where the real work is done.
level 0 level 1
level 2
level h
Sifting down each level requires 2 comparisons: one between the children, and one between the larger child and the parent
In the worst case, the top item may be sifted all the way up to the bottom, or h levels,
for a total of 2*h comparisons.
Since h = log2(n+1) – 1, the total number of comparisons is 2*(log2(n+1) – 1) ≡ 𝑂(log 𝑛)
The total time for delete is O(1) + 𝑂(log 𝑛) = 𝑂(log 𝑛)
(We are not counting swaps. Since a swap is only done when a comparison is done,
the number of comparisons is a proxy for swaps as well, and it does not change the big O)
Sesh Venugopal CS 112: Heap Operations 16