🏔️🚀
Heap: A complete binary tree where the "Best" item (Max or Min) stays at the root. Perfect for Priority Queues where you always need to extract the highest priority item in O(log n) time.
Heap Type:
Speed:
Nodes: 0
Root: —
Height: 0
🏔️
Heap is empty
Insert a number to see the heap build!
Array Representation
Index: [i] -> Left: [2i+1], Right: [2i+2]
Insert Item
Randomize:
Extract Root
Removes root and "Heapifies" to maintain property.
🏔️
OS Ready
Enter a value to begin Heap operations.
🔑 Heap Constraint
Max Heap: Every parent node must be Greater than or Equal to its children.
The tree is always nearly complete (filled level-by-level).
🏔️
Binary Heap & Priority Queue
The foundation of efficient "Top N" algorithms
🌳
Unlike a BST, a Heap is NOT sorted from left to right.
⚖️
It only cares about the relationship between Parent and Child. In a Max-Heap, parents are always ≥ children.
🏗️
A Heap is always Complete: every level is full except possibly the last, which is filled from left to right.
💡
This makes it easy to store in a simple 1D array with no pointers needed!
0️⃣
Root is stored at index 0.
⬅️
Left child of index
i is at 2*i + 1.➡️
Right child of index
i is at 2*i + 2.⬆️
Parent of index
i is at floor((i-1)/2).➕
Insert (Shift Up): Add to the last spot, then swap upwards until the parent is bigger.
➖
Extract (Shift Down): Remove root, move the last leaf to root, then swap downwards to restore balance.
⏱️
Both operations take O(log n) time.
🎯
Priority Queues: Handling tasks based on urgency (e.g., Hospital triage).
📊
Heap Sort: A comparison-based sorting algorithm using a Heap.
🗺️
Graph Algorithms: Dijkstra's Shortest Path uses Heaps to pick the next closest node efficiently.
🖥️
OS Scheduling: Managing processes based on their priority level.