What does a heap do?

In this tutorial, we'll learn about heaps, a very interesting data structure. Heaps are a data-structure that efficiently support the following operations

1. Insert / Push: Insert a new element to a set
2. Delete-min / Pop: Find and remove the smallest element in the set

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}         | 2      
heap.pop()       | {10}            | 5      
heap.insert(7)   | {10, 7}         |        
heap.insert(12)  | {10, 7, 12}     |        
heap.pop()       | {10, 12}        | 7      
heap.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.

Max-heaps

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.

Illustration in Python

import heapq
 
heap = []
 
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}

Can we use a list / array instead?

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.

Heap-sort

Before we get into heaps, let's see how heap-sort would work assuming we have a heap.

define heapsort(array):
    heap = empty heap 
    for element in array:
        heap.insert(element)
    sorted = empty list 
    while heap is not empty
        sorted.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.

Other applications of heaps

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).

How do heaps work?

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).

Heap property

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.

How are heaps stored?

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 floor(p/2).

Insert operation

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 heap
    while 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.

Delete-min operation

Finally, here's the pseudocode for the delete-min operation

define pop()
    top = value at root
    remove last node of the heap and store value at the root
    node = root 
    while 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 46 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.

Conclusion

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.

References

1. Priority Queues - Ray Toal | Loyola Marymount University