Heap & Priority Queue Data Structure
A Heap is a complete binary tree structure satisfying the heap property: in a Max Heap, every parent node is greater than or equal to its children.
Max Heap Insertion & Bubble Up Step-by-Step
Insert Value at Array End
Append new element 60 at end of complete binary tree array.
Array: [50, 30, 20, 60] (Inserted 60 at index 3)Compare with Parent Node
Parent of index 3 is index 1 (value 30). Since 60 > 30, heap property is violated.
Compare: Child(60) > Parent(30) -> Swap requiredBubble Up to Root
Swap 60 and 30. Then compare 60 with root 50. Swap 60 and 50 so 60 becomes root.
Heap Array: [60, 50, 20, 30] (Max Heap property restored)Real-world analogy: Hospital ER Triage
Patients entering emergency triage are prioritized by illness severity. The most urgent patient is always treated next regardless of arrival time.
- Max Heap= Root contains the maximum element in the dataset.
- Heapify= Rebalances parent and child nodes after insertions or extractions.
Operations explained
Complexity analysis
~9 steps (Logarithmic)
O(log N) Tree Height Time
O(N) Tree Nodes Space
Memory growth rate as N expands.
Relative efficiency rating for large N.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Extract Max / Min | O(log N) | O(1) |
| Get Max / Min | O(1) | O(1) |
| Build Heap | O(N) | O(1) |
Code implementations
class MinHeap {
constructor() { this.heap = []; }
push(val) { this.heap.push(val); this.bubbleUp(); }
pop() { /* extract top */ }
}Real-world applications
Priority Queue
Schedules OS CPU tasks by urgency ranks.
Dijkstra Algorithm
Selects minimum distance graph vertex dynamically.
Interview questions
Topic Knowledge Test & Assessment
Heap Knowledge & Skill Test
Validate your conceptual understanding, operation mechanics, and core concepts of Heap.
Topic Metadata
Building a heap from an unsorted array of N elements takes linear time O(N) using bottom-up Floyd's heap construction!