Intro
Heaps are Tree-based data structure. A Heap must be a complete tree and satisfy its type’s properties.
Types
Max Heap
The value of the parent node must be greater than its child nodes’ values. Meaning the Root is the largest value in this heap’s tree.
Min Heap
The value of the parent node must be less than its child nodes’ values. Meaning the Root is the smallest value in this heap’s tree.
Heaps and Priority Queues
In some contexts these ae treated the same.
Time complexity
| Operation | Big-O |
|---|---|
| Find max/min | O(1) |
| Insert | O(log(n)) |
| Remove | O(log(n)) |
| Heapify (create a heap out of given array of elements) | O(n) |
Techniques
Mention of k
Questions containing “lowest k” or “top k” are often a good signal that a heap can be used to solve. See Top K Frequent Elements.
Example: If you require the Top k elements.
- Use a Min Heap of size k.
- Iterate through each element, pushing it into the heap.
(for python
heapq, invert the value before pushing to find the max). // not sure what this means? - Whenever the heap size exceeds k, remove the minimum element, that will guarantee that you have the k largest elements.