Beginner LevelData Structures & Algorithms
What is a Heap (Min-Heap / Max-Heap) and how is it used as a Priority Queue?
ā Interview Prompt: Explain Heap structure, heap property, O(log N) push/pop, O(1) peek, and the K largest / K smallest elements problem.
A Heap is a complete binary tree stored as an array satisfying the heap property:
ā¢
Max-Heap: Parent ā„ children (root = maximum element).
ā¢
Min-Heap: Parent ā¤ children (root = minimum element).
Key Operations:
| Operation | Time |
|---|---|
| Insert (sift-up) | $O(\log N)$ |
| Remove root (sift-down) | $O(\log N)$ |
| Peek (root) | $O(1)$ |
| Build heap (heapify) | $O(N)$ |
Parent/Child Index in Array (0-indexed):
ā¢
Parent of $i$:
Math.floor((i - 1) / 2)ā¢
Left child:
2i + 1, Right child: 2i + 2Code Implementation Example
typescript
// Find K largest elements using a Min-Heap of size K ā O(N log K)
// (In interviews, simulate with a sorted structure or JS arr.sort)
function kLargest(nums: number[], k: number): number[] {
// Use a Min-Heap of size K: maintain K largest seen
const heap: number[] = [];
for (const n of nums) {
heap.push(n);
heap.sort((a, b) => a - b); // simulated min-heap
if (heap.length > k) heap.shift(); // pop minimum
}
return heap; // remaining K elements are largest
}
// Proper heap gives O(N log K); this simulation is O(N K log K) ā for illustration
console.log(kLargest([3, 1, 5, 12, 2, 11], 3)); // [5, 12, 11]š”K Largest Elements using a Min-Heap of size K.
šÆ Interview Key Takeaway
Use a Min-Heap of size K for K-largest problems. Heap sort achieves O(N log N) with O(1) space ā an in-place advantage over Merge Sort.
#DSA#Heap#Priority Queue#Min-Heap#Beginner
Back to all Data Structures & Algorithms Questionsā