1.
Introduction to Heap
A Heap is a special complete binary tree that satisfies the heap property.
🔹 Heap Property:
For Max Heap → Every parent node’s value is greater than or equal to its children.
For Min Heap → Every parent node’s value is less than or equal to its children.
🔹 Complete Binary Tree:
A tree is complete if all levels are filled except possibly the last, and the last level has all
nodes as far left as possible.
🔹 Example:
Max Heap example:
50
/ \
30 40
/ \ /
10 20 35
Here, each parent is greater than its children.
Min Heap example:
10
/ \
20 15
/ \ /
30 40 50
🌲 2. Types of Heaps
1. Min Heap
o Smallest element is at the root.
o Useful for applications where we repeatedly need the minimum element (like
Dijkstra’s algorithm).
2. Max Heap
o Largest element is at the root.
o Useful for applications where we repeatedly need the maximum element (like
heap sort).
🧮 3. Heap Representation
A heap can be efficiently represented using an array because it is a complete binary tree.
Let’s assume array index starts from 0.
Node Position Formula
Left Child 2*i + 1
Right Child 2*i + 2
Parent (i - 1) / 2
Example:
For array [50, 30, 40, 10, 20, 35]
50
/ \
30 40
/ \ /
10 20 35
⚙️4. Heap Operations
🔸 Insertion
Goal: Insert a new element while maintaining the heap property.
Steps (Max Heap Example):
1. Add the new element at the next available position (bottom-most, left-most).
2. Compare it with its parent.
3. If it violates heap property → Swap.
4. Repeat until heap property is restored (this is called heapify-up or bubble-up).
Example:
Insert 45 into:
50
/ \
30 40
→ Insert 45 as left child of 30
→ Compare 45 with parent 30 → swap
→ Now heap becomes:
50
/ \
45 40
30
Time Complexity: O(log n)
🔸 Deletion (Extract Max or Extract Min)
Goal: Remove the root element (highest or lowest).
Steps (Max Heap Example):
1. Replace the root with the last element.
2. Delete the last element.
3. Perform heapify-down — compare with children and swap with the larger child until
heap property holds.
Example:
Delete root (50) from:
50
/ \
45 40
30
→ Replace 50 with 30
→ Compare 30 with 45 → swap
→ Heap after deletion:
45
/ \
30 40
Time Complexity: O(log n)
🔸 Peek (Get Max / Get Min)
Simply return the root element.
Time Complexity: O(1)
🔸 Heapify
Definition: Convert an array into a heap.
Two methods:
1. Top-down approach: Insert elements one by one and heapify-up each time → O(n
log n)
2. Bottom-up approach: Start from the last non-leaf node and heapify-down → O(n)
Example:
Array [4, 10, 3, 5, 1]
→ Heapify from last non-leaf node (index = n/2 - 1)
🧩 5. Heap Construction
Algorithm (Bottom-Up):
for i = (n/2) - 1 down to 0:
heapify(array, n, i)
This ensures all subtrees satisfy heap property.
Time Complexity: O(n)
🔄 6. Heap Sort Algorithm
Concept:
Use heap structure to sort an array.
Steps:
1. Build a Max Heap from the array.
2. Swap the first (largest) element with the last.
3. Reduce heap size by 1.
4. Heapify the root again.
5. Repeat until sorted.
Example:
Array: [4, 10, 3, 5, 1]
1. Build Max Heap → [10, 5, 3, 4, 1]
2. Swap 10 ↔ 1 → [1, 5, 3, 4, 10]
3. Heapify → [5, 4, 3, 1, 10]
4. Continue → Sorted array [1, 3, 4, 5, 10]
Time Complexity: O(n log n)
📦 7. Priority Queue using Heap
Definition:
A priority queue is an abstract data type where each element has a priority.
Elements with higher priority are dequeued first.
Implementation:
Using Max Heap: highest value = highest priority.
Using Min Heap: smallest value = highest priority.
Operations:
insert(element, priority) → O(log n)
extract_max() or extract_min() → O(log n)
peek() → O(1)
Applications:
CPU task scheduling
Dijkstra’s shortest path algorithm
Event simulation systems
🧠 8. Applications of Heaps
Heap Sort
Priority Queue
Dijkstra’s Algorithm (shortest path)
Prim’s Algorithm (minimum spanning tree)
Find k-th largest/smallest element
Median in a data stream
🔺 9. Variants of Heap (Advanced)
Type Description Application
Binary Heap 2 children per node General use
d-ary Heap Each node has d children Better for dense graphs
Binomial Heap Collection of binomial trees Mergeable heaps
Fibonacci Heap Highly efficient for decrease-key Used in Dijkstra’s & Prim’s
Pairing Heap Simplified Fibonacci heap Fast practical performance
🧾 10. Time & Space Complexity Summary
Operation Binary Heap Description
Insert O(log n) Heapify-up process
Delete (Extract) O(log n) Heapify-down process
Get Min/Max O(1) Root access
Build Heap O(n) Bottom-up heapify
Heap Sort O(n log n) Sorting algorithm
Space Complexity O(n) Array storage
#include <stdio.h>
#define MAX 100 // Maximum size of heap
int heap[MAX];
int size = 0; // Current number of elements in heap
// ---------------------- FUNCTION DECLARATIONS ----------------------
void insert(int value);
void deleteRoot();
void heapify(int heap[], int n, int i);
void buildHeap(int heap[], int n);
void heapSort(int heap[], int n);
void display();
// ---------------------- INSERTION ----------------------
void insert(int value) {
if (size >= MAX) {
printf("Heap is full!\n");
return;
// Insert the new value at the end
size++;
int i = size - 1;
heap[i] = value;
// Heapify Up (bubble-up)
while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
int temp = heap[i];
heap[i] = heap[(i - 1) / 2];
heap[(i - 1) / 2] = temp;
i = (i - 1) / 2;
// ---------------------- DELETION (Delete Root) ----------------------
void deleteRoot() {
if (size <= 0) {
printf("Heap is empty!\n");
return;
int root = heap[0];
heap[0] = heap[size - 1];
size--;
// Heapify Down
heapify(heap, size, 0);
printf("Deleted root element: %d\n", root);
// ---------------------- HEAPIFY FUNCTION ----------------------
void heapify(int heap[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If left child is greater than root
if (left < n && heap[left] > heap[largest])
largest = left;
// If right child is greater than current largest
if (right < n && heap[right] > heap[largest])
largest = right;
// If largest is not root
if (largest != i) {
int temp = heap[i];
heap[i] = heap[largest];
heap[largest] = temp;
// Recursively heapify the affected sub-tree
heapify(heap, n, largest);
// ---------------------- BUILD HEAP (BOTTOM-UP) ----------------------
void buildHeap(int heap[], int n) {
int startIdx = (n / 2) - 1;
// Perform reverse level order traversal from last non-leaf node
for (int i = startIdx; i >= 0; i--) {
heapify(heap, n, i);
// ---------------------- HEAP SORT ----------------------
void heapSort(int heap[], int n) {
buildHeap(heap, n);
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
// call heapify on the reduced heap
heapify(heap, i, 0);
// ---------------------- DISPLAY FUNCTION ----------------------
void display() {
printf("Heap elements: ");
for (int i = 0; i < size; i++)
printf("%d ", heap[i]);
printf("\n");
}
// ---------------------- MAIN FUNCTION ----------------------
int main() {
int choice, value, n, i;
while (1) {
printf("\n=== HEAP OPERATIONS MENU ===\n");
printf("1. Insert\n");
printf("2. Delete Root\n");
printf("3. Display Heap\n");
printf("4. Build Heap from Array\n");
printf("5. Heap Sort\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insert(value);
break;
case 2:
deleteRoot();
break;
case 3:
display();
break;
case 4:
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements: ");
for (i = 0; i < n; i++)
scanf("%d", &heap[i]);
size = n;
buildHeap(heap, n);
printf("Heap constructed successfully!\n");
break;
case 5:
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements: ");
for (i = 0; i < n; i++)
scanf("%d", &heap[i]);
heapSort(heap, n);
printf("Sorted elements: ");
for (i = 0; i < n; i++)
printf("%d ", heap[i]);
printf("\n");
break;
case 6:
return 0;
default:
printf("Invalid choice!\n");
