A Heap is a specialized tree-based data structure that satisfies the heap property. In a Min Heap, for any given node, the value of that node is less than or equal to the values of its children. In a Max Heap, the value is greater than or equal to its children. Heaps are typically implemented as complete binary trees using arrays for efficient storage.
The heap property ensures that the minimum (or maximum) element is always at the root, making heaps ideal for priority queues and heap sort algorithms. Operations like insertion and extraction maintain the heap property through heapify operations with O(log n) time complexity.
Insert: Enter a number and click "Insert" to add it to the heap.
Extract Root: Remove and return the minimum (Min Heap) or maximum (Max Heap) element.
Toggle Heap Type: Switch between Min Heap and Max Heap (rebuilds existing heap).
Build from Array: Enter comma-separated numbers to build a heap at once.
Visual Indicators: Root node is highlighted in blue. Index [i] shows array position.
Heapify Up: After insertion, compare with parent and swap if needed, repeat up the tree.
Heapify Down: After extraction, move last element to root, compare with children and swap with smaller/larger child.
Build Heap: Start from last non-leaf node and heapify down to root (O(n) operation).
Array Index Formula: For node at index i: Left = 2i+1, Right = 2i+2, Parent = ⌊(i-1)/2⌋
Complete Tree: Heap fills left to right, no gaps in levels except possibly last level.
Priority Queues: Operating system task scheduling, hospital emergency rooms.
Heap Sort: Efficient O(n log n) sorting algorithm with O(1) space.
Dijkstra's Algorithm: Finding shortest paths in graphs using min heap.
Median Maintenance: Finding running median using two heaps (max + min).
Event-Driven Simulation: Managing events by timestamp priority.
Insert: Add element at end, then heapify up - O(log n).
Extract Min/Max: Remove root, move last to root, heapify down - O(log n).
Peek: Return root element without removing - O(1).
Build Heap: Convert array to heap using bottom-up heapify - O(n).
Heapify: Restore heap property at a node by comparing with children.
Decrease/Increase Key: Update value and heapify up or down as needed.
K Largest/Smallest: Use min heap of size k for k largest; max heap for k smallest.
Merge K Sorted Lists: Use min heap to always get smallest among k list heads.
Running Median: Use max heap for lower half, min heap for upper half; balance sizes.
Top K Frequent: Count frequencies, then use heap to get top k by frequency.
Task Scheduler: Use max heap to schedule most frequent tasks first with cooldown.
Kth Largest in Stream: Maintain min heap of size k; root is always kth largest.
Reorganize String: Use max heap to place most frequent characters with gaps.
/* Min Heap implementation in C */
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *arr;
int size;
int capacity;
} MinHeap;
MinHeap* createHeap(int capacity) {
MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
heap->arr = (int*)malloc(sizeof(int) * capacity);
heap->size = 0;
heap->capacity = capacity;
return heap;
}
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
void heapifyUp(MinHeap* heap, int index) {
int parent = (index - 1) / 2;
while (index > 0 && heap->arr[index] < heap->arr[parent]) {
swap(&heap->arr[index], &heap->arr[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
void heapifyDown(MinHeap* heap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heap->size && heap->arr[left] < heap->arr[smallest])
smallest = left;
if (right < heap->size && heap->arr[right] < heap->arr[smallest])
smallest = right;
if (smallest != index) {
swap(&heap->arr[index], &heap->arr[smallest]);
heapifyDown(heap, smallest);
}
}
void insert(MinHeap* heap, int value) {
if (heap->size >= heap->capacity) return;
heap->arr[heap->size] = value;
heapifyUp(heap, heap->size);
heap->size++;
}
int extractMin(MinHeap* heap) {
if (heap->size <= 0) return -1;
int min = heap->arr[0];
heap->arr[0] = heap->arr[--heap->size];
heapifyDown(heap, 0);
return min;
}
int main() {
MinHeap* heap = createHeap(10);
insert(heap, 3); insert(heap, 1); insert(heap, 6);
insert(heap, 5); insert(heap, 2); insert(heap, 4);
printf("Extract min: %d\n", extractMin(heap)); // 1
printf("Extract min: %d\n", extractMin(heap)); // 2
return 0;
}