Heap Data Structure
A heap is a tree-based data structure that maintains properties such that either the maximum or minimum value from a set can be retrieved efficiently.
The two types of heaps are:
- Min heap - The root node of each subtree is the smallest element.
- Max heap - The root node of each subtree is the largest element.
A heap is a complete binary tree, which means all the levels in the tree are filled (have both left and right nodes), except the last level.
The 4 main operations of a heap are:
- Get min - Get the root element of the heap (the max element in the case of a max heap)
- Push - Add an element to the heap. Newly added nodes are placed in the next available position in the tree to maintain its completeness. The node is then swapped with its parent until it is smaller than its children, and the heap property is maintained.
- Pop - Remove and retrieve the root element of the heap (the smallest element in a min heap, the largest in a max heap). The heap is reorganized such that the next smallest number becomes the root, maintaining the heap property.
- Heapify - Convert an iterable (a list for example) into a heap by reordering the elements.
Heap Big O
Both min and max heaps have the same time complexity. So let's take a look at a min heap Big O:
|Operation||Worst Case Time|
In Python, the best way to use a heap is the
If you want to convert an iterable to a heap:
To pop the smallest number off the heap, we can use
We can add a new person's age to our heap with
If we want to just retrieve the smallest number without popping it off, the root is in the first position of a heapified iterable:
heapqoperates as a min heap under the hood. To use a max heap, simply negate the values before they enter the heap.
And remember to negate again when reading from the max heap.