- 1.Heaps are a data structure that enables us to efficiently track the minimum or maximum in a collection of elements, even as that collection changes.
- 2.Heaps are commonly used to implement priority queues for use cases such as hospital queues, bank queues and process queues in operating systems.
heapqlibrary when we are ready to solve heap problems.
Heaps are a data structure that enables us to efficiently track the minimum ("min heap") or maximum ("max heap") in a collection of elements, even as that collection changes. Heaps are commonly used to implement "priority queues" for use cases such as hospital queues, bank queues and process queues in operating systems. In these scenarios, heaps enable us to determine which person/element should be at the front of the queue based on factors in addition to insertion order such as severity or importance.
The beauty of heaps is that they enable us to extract the minimum (in a min heap) or maximum (in a max heap) value in
O(1)time, while inserting new values into a heap takes
O(logn)time. This is more efficient than adding a new element in sorted order to a sorted array, which would take
O(n)time. Heaps are able to do this by utilising properties of trees, where heap elements are only partially sorted and not completely sorted like they would be in a sorted array.
The following video explains what heaps look like in theory and the fundamental properties of heaps that enable heaps to maintain
O(1)access to the min or a max element efficiently. The video uses a max heap as an example, but the same properties apply to min heaps except with the order reversed (smaller numbers on top).
Introduction to heaps and how heaps maintain
O(1)access to min or max element when new element added
The following video explains how heaps maintain
O(1)access to the min or max element when the previous min or max element is removed. Again the video uses a max heap as an example but the same theory applies to min heaps, except with order reversed.
How heaps maintain
O(1)access to min or max element after removal of previous min or max element
The above videos may not have mentioned, but notice the time complexity of adding or removing an element from the heap is
O(logn)because we only perform element swaps down a single path of the heap tree, through
nis the number of elements in the heap.
Now that we've learnt the theory, you may be wondering how to implement heaps in practice. The following video explains how to efficiently represent the heap data structure in code using an array.
How to represent and use heaps in code with arrays
Rocket recommends we focus on mastering other data structures and algorithms first before attempting heap problems. When ready to solve heap problems, Rocket recommends we use Python and its built-in
removerespectively in JS code example above) are implemented for us.
Please review Rocket's Python submodule before working on heap algorithm exercises with
heapqdata structure is a min heap by default. To use
heapqas a max heap with numerical values, multiply every number you insert by -1 on push and pop.
- 2.We may wish to sort elements by certain numerical values in a heap, but store associated payloads along with those numerical values. In these situations we can insert tuples (e.g.
(x, y)) into our heap, where
xis the value to sort by and
yis the associated payload. For example, in the K Closest Points to Origin problem below, we could store
(dist_to_origin, coordinates)elements in our heap.
- 3.A common pattern when solving problems asking for the "max K elements" of anything is to use the reverse kind of heap and maintain the heap size as K. For example, if the problem is asking for "max K elements", we can keep a min heap of size K that stores the max K elements seen so far. Keeping a min heap allows us to find the minimum of the max K elements in constant time, saving us from pushing and popping to our heap if the new element is not within the max K elements so far.
- 1.We can do
heapto quickly peek at the min element in a min heap or the max element in a max heap.
- 2.Conversely, if the problem asks for "min K elements" we can use a max heap of size K.
- 4.Heaps are not always necessary. Given a static input list, it may be faster to sort the input list and access the Kth element instead of using a heap. Heaps are most useful when we may not have the full input up front.
- 1.Kth Largest Element in Array (LeetCode)
- 1.Hint: What's the most efficient way to get the Kth largest element in a heap of size K? Would we use a min-heap or max-heap? Review tips above before starting.