Heap Operations Time Complexity
Heap operations — insertion, deletion, and heapify — have specific time complexities that appear frequently in algorithms courses, FAANG interview prep, and competitive programming. Understanding why these bounds hold and how min-heaps and max-heaps differ is essential for priority queue implementations and sorting algorithms like heapsort.
Interactive Deck
5 CardsHeap peek (find min/max) complexity?
Min-heap vs max-heap property?
Master this topic effortlessly.
Study G helps you master any topic effortlessly using proven learning algorithms and smart review timing
Download Study GFrequently Asked Questions
Why is heap insertion O(log n) instead of O(n)?
A heap is a complete binary tree with height O(log n). Insertion adds the element at the bottom and sifts it up at most O(log n) levels, comparing with one parent per level.
Why is build heap O(n) and not O(n log n)?
Bottom-up heapify starts from the last non-leaf node and sifts down. Most nodes are near the leaves with short paths — the total work sums to O(n) by a geometric series argument.
What is the difference between a heap and a BST?
A heap only guarantees parent-child order (root is min or max), enabling O(1) access to the extreme. A BST maintains full sorted order, supporting O(log n) search but O(log n) min/max.
- Heap: O(1) min/max, no search
- BST: O(log n) search, O(log n) min/max