Heaps Flashcards
min heap
min at top. parent node value <= value of the child nodes.
min heap is the default in python
heap insertion time complexity
worst case O(log n)
heap delete node time complexity
worst case O(log n)
heap lib in python
heapq which is short for heap queue which is also an implementation of priority queue. MIN heap.
solution to kth largest element
import heapq heapq.nlargest(k, nums)[-1]
nlargest returns items in descending order (even though heapq is a MIN heap). return k items then take the tail.
Tell me about heaps
- Mainly used to represent a priority queue
- Heaps are complete binary trees (all the levels are completely filled except possibly the lowest one which is filled from left to right)
Representing a heap as an array
Use level ordering to complete the array
Max heap
the parent node value >= value of the child node
How do you convert a heap into an array?
Use level order
Return parent node of heap array
a[ (i-1) // 2 ]
Return left child node of heap array
a[ 2i + 1 ]
Return right child node of heap array
a[ 2i + 2 ]
convert array heap to tree struct
import heapq as hq
hq.heapify(array)
add item to heap tree
import heapq as hq
heappush
remove item from heap tree
import heapq as hq
heappop
throws exception if heap is empty
