In this tutorial, we'll learn about heaps, a very interesting data structure. Heaps are a data-structure that efficiently support the following operations
Note that the operations can be performed multiple times and in any order. (Also, note that actual implementations also support operation top, which returns the smallest element, but does not remove it from the heap).
The following is a sample interaction we would want with a heap.
code | set of elements | result-----------------|-----------------|--------heap = Heap() | {} |heap.insert(5) | {5} |heap.insert(2) | {5, 2} |heap.insert(10) | {5, 2, 10} |heap.pop() | {5, 10} | 2heap.pop() | {10} | 5heap.insert(7) | {10, 7} |heap.insert(12) | {10, 7, 12} |heap.pop() | {10, 12} | 7heap.pop() | {12} | 10
It doesn't matter how the set is stored. What matters is that we always get the correct result. A heap can perform both the operations above in O(\log n) time per operation, where n is the number of elements currently in the set.
In this article, we are talking about min-heaps. But similarly, we can also define max-heaps which remove the largest element instead of the smallest element.
import heapqheap = []heapq.heappush(heap, 5) # set = {5}heapq.heappush(heap, 2) # set = {5, 2}heapq.heappush(heap, 10) # set = {5, 2, 10}heapq.heappop(heap) # result = 2. set = {5, 10}heapq.heappop(heap) # result = 5. set = {10}heapq.heappush(heap, 7) # set = {10, 7}heapq.heappush(heap, 12) # set = {10, 7, 12}heapq.heappop(heap) # result = 7. set = {10, 12}heapq.heappop(heap) # result = 10. set = {12}
Note that if we use a list to perform the above operations, then the first operation (insert) can be done in O(1), but the second operation (finding the removing the minimum) takes O(n). If instead we always maintain a sorted list, then finding and removing the minimum takes O(1), but inserting a new element takes O(n).
So, if we have equal number of operation 1 and operation 2, then lists take time O(qn), whereas the heap takes O(q \log n), where q is the total number of operations.
Before we get into heaps, let's see how heap-sort would work assuming we have a heap.
define heapsort(array):heap = empty heapfor element in array:heap.insert(element)sorted = empty listwhile heap is not emptysorted.append(heap.pop())return sorted
That is, we do n insert operations, and then n pop operations. Since each operation is O(\log n), heap sort takes O(n \log n) time total.
Heap-sort is only one application of a heap. There are many other important applications of heaps. Most notably, these include (a) Dijkstra's shortest-path algorithm for weighted graphs, (b) Prim's Minimum Spanning Tree algorithm, (c) as priority queues (data structures that support the above two heap operations).
The heap data structure is a binary tree (each internal node has two children). Also, it is balanced, which means that new nodes are added layer by layer, left to right (see image below).
Lastly, note that some of nodes will have 0 children (these are called leaves), and it is possible for one of the nodes to have exactly 1 child (node with value 46 in the image above).
The heap data structure's efficiency comes because of maintaining the heap property. The property is: for every node, the value at the parent is less than or equal to the value at the children. For example, in the image above, 9 is smaller than both it's children, 26 and 11. Similarly, 18 is smaller than both it's children, 30 and 19.
Because of the heap property, the minimum value in the heap is always at the root node.
Although heaps nodes form a binary tree, it is in-fact possible to implement heaps efficiently while storing all elements in an array. The elements in the array would be listed layer-by-layer, left to right. For example, the array corresponding to the above heap is:
3 9 4 26 11 18 20 35 46 12 15 30 19 26 24 71 80 52
Assuming that array indexes begin at 1, the children of position p are at 2p and 2p+1. The parent of position p is at position int(p/2).
Now we'll see how to perform the insert and delete-min operations in O(\log n) time while maintaining the heap property. We'll start with the insert operation. Here's the pseudocode
define insert(element)insert element to the first empty position in the heapwhile element's parent is larger than element:swap(element, parent)
Let's see an example. In the example, we insert 5 as a new leaf. To resolve this, we swap 5 with 46, then with 26, then with 9, and then stop (since 3 is smaller than 5).
At any point, the only possible place where the heap property is violated is between 5 and it's current parent, which is resolved when all the upward-swaps are completed.
No other new violations are introduced between other nodes. For example, when we swap 5 and 46, 5 and 52 cannot violate the heap property since 5 is smaller than 46, and 46 is smaller than 52.
Finally, here's the pseudocode for the delete-min operation
define pop()top = value at rootremove last node of the heap and store value at the rootnode = rootwhile either of node's children is smaller than node:swap(node, whichever child is smaller)
Let's see an example below. Suppose we do the delete-min operation on our heap. The minimum value 3 is at the root. We need to remove this value which reduces the total number of nodes in the heap. So we remove the last element (46) and put the value at position 3. Because of this, the heap property might be violated between 46 and it's children.
To fix this, swap 46 with whichever child is smaller. The first swap is 46 and 4. Then 46 and 18. Then 49 and 19. At any point, the only possible place where the heap property is violated is between 46 and it's current children, which is resolved when all the downward-swaps are completed.
Heaps are a powerful and important data structure. In this tutorial, we saw how they support the insert and delete-min operations in O(\log n) time per operation. They achieve this by storing all the elements in a binary tree of height \log n which always maintains the heap property.
In the next tutorial, we'll implement the heap data-structure from scratch and use it to perform heap-sort.
