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.