MediumHigh Frequency20 min
Heap Fundamentals
Min-heap vs max-heap, heapify, and why heaps give O(log n) push/pop.
Heap means priority queue. The root is always the smallest item in a min-heap or the largest item in a max-heap.
Heap Basics
Operation Complexities
Operation
Time
Note
peek
O(1)
Read the root
insert
O(log n)
Append then bubble up
extract root
O(log n)
Move last item to root then sift down
heapify
O(n)
Build from an existing array
search arbitrary value
O(n)
Heap is not fully sorted