A heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property:
- in a max heap, for any given node
Pis a parent node of
C, then the key (the value) of
Pis greater than or equal to the key of
- in a min heap, the key of
Pis less than or equal to the key of
The node at the “top” of the heap (with no parents) is called the root node.
Heaps are usually implemented with an array, as follows:
- Each element in the array represents a node of the heap, and
- The parent / child relationship is defined implicitly by the elements’ indices in the array.
Given a node at index
- its children are at indices
2i + 1and
2i + 2, and
- its parent is at index
O(n) time complexity but
O(nlog(n)) time complexity.
- We call
heapify, which takes
nelements, but the time complexity of building heap comes out to be
- The main idea is that in the
build_heapalgorithm the actual
heapifycost is not
O(log(n))for all elements.
The common operations involving heaps are:
find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
adding a new key to the heap (a.k.a., push)
returns the node of maximum value from a max heap [or minimum value from a min heap] after removing it from the heap (a.k.a., pop)
removing the root node of a max heap (or min heap), respectively
pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps.
create an empty heap
create a heap out of given array of elements
joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps.
joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
return the number of items in the heap.
return true if the heap is empty, false otherwise.
updating a key within a max- or min-heap, respectively
delete an arbitrary node (followed by moving last node and sifting to maintain heap)
move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called “sift” because node moves up the tree until it reaches the correct level, as in a sieve.
move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.
|Binary||Θ(1)||Θ(log n)||O(log n)||O(log n)||Θ(n)|
|Binomial||Θ(1)||Θ(log n)||Θ(1)||Θ(log n)||O(log n)|
- Priority queues can be efficiently implemented using Binary Heap.
- Binomial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in
O(logn)time which is a
O(n)operation in Binary Heap.
- Order Statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array. https://en.wikipedia.org/wiki/K-way_merge_algorithm
MinHeap Implementation in Python
Using Python’s heapq library
min_heap, see code below:
Kth largest or smallest
Do not use this when doing heap problems this creates a min heap everytime
This library supports
min_heap implementation, to make
max_heap multiply each element with
Push custom object with
If the object implements comparison operators, you can push your custom objects into the heap.
In case you are not able to update/implement class definition, you can use tuple to push custom objects, wherein the first member of the tuple is the comparison key.
heapq.heappush(heap, (l.val, l)), here
lis a class object (lets say linked-list)
The problem with putting
(l.val, l)on the heap is that when two tuples’s first member have the same value, then a comparison will happen between the second member values, i.e. between
Either make sure your first member will never have a conflict (this shall throw runtime error) or you can introduce a third member (unique value) in those tuples, between the two members you already have.
heapq.heappush(heap, (l.val, i, l))
But remember if the second member will have conflict this too shall throw runtime error.