Binary Heaps – Complete Notes

With C Code, Diagrams, Operations, and Applications

Binary Heaps – Complete Notes

With C Code, Diagrams, Operations, and Applications

Binary Heaps – Complete Notes

With C Code, Diagrams, Operations, and Applications

1. What is a Binary Heap?

Binary Heap is a complete binary tree that satisfies the heap property.

Two Types

Type Property
Max-Heap Parent ≥ Children
Min-Heap Parent ≤ Children

Complete Binary Tree

  • All levels filled except possibly the last
  • Last level filled left to right
         100
       /     \
     80       70
    /  \     /  \
  60   50   40   30

2. Array Representation

Root at index 1 (or 0)
For node at index i:
- Left Child: 2*i
- Right Child: 2*i + 1
- Parent: i/2

Max-Heap Array

Index:  1   2   3   4   5   6   7
      [100,80,70,60,50,40,30]

3. Heap Operations

Operation Time
insert() O(log n)
extractMax/Min() O(log n)
peek() O(1)
heapify() O(log n)
buildHeap() O(n)

4. Core Functions

A. Heapify (Down) – Maintain heap property

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;

    if (left <= n && arr[left] > arr[largest])
        largest = left;
    if (right <= n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

B. Insert

void insert(int arr[], int* n, int value) {
    (*n)++;
    arr[*n] = value;
    int i = *n;

    // Heapify Up
    while (i > 1 && arr[i] > arr[i/2]) {
        swap(&arr[i], &arr[i/2]);
        i = i / 2;
    }
}

C. Extract Max

int extractMax(int arr[], int* n) {
    if (*n == 0) return -1;

    int max = arr[1];
    arr[1] = arr[*n];
    (*n)--;

    heapify(arr, *n, 1);
    return max;
}

D. Build Heap from Array

void buildHeap(int arr[], int n) {
    for (int i = n / 2; i >= 1; i--)
        heapify(arr, n, i);
}

Time: O(n) (not O(n log n))

5. Full C Implementation (Max-Heap)

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;

    if (left <= n && arr[left] > arr[largest])
        largest = left;
    if (right <= n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void insert(int arr[], int* n, int value) {
    (*n)++;
    arr[*n] = value;
    int i = *n;
    while (i > 1 && arr[i] > arr[i/2]) {
        swap(&arr[i], &arr[i/2]);
        i /= 2;
    }
}

int extractMax(int arr[], int* n) {
    if (*n == 0) return -1;
    int max = arr[1];
    arr[1] = arr[*n];
    (*n)--;
    heapify(arr, *n, 1);
    return max;
}

void printHeap(int arr[], int n) {
    for (int i = 1; i <= n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int heap[100];
    int n = 0;

    insert(heap, &n, 10);
    insert(heap, &n, 30);
    insert(heap, &n, 20);
    insert(heap, &n, 50);
    insert(heap, &n, 40);

    printf("Max-Heap: ");
    printHeap(heap, n);  // 50 40 20 10 30

    printf("Extract Max: %d\n", extractMax(heap, &n));  // 50
    printf("After extract: ");
    printHeap(heap, n);  // 40 30 20 10

    return 0;
}

6. Min-Heap (Just Change Comparison)

// In heapify and insert, change > to <
if (left <= n && arr[left] < arr[smallest])  // Min-Heap

7. Heap Sort

void heapSort(int arr[], int n) {
    // Build max-heap
    for (int i = n / 2; i >= 1; i--)
        heapify(arr, n, i);

    // Extract max one by one
    for (int i = n; i > 1; i--) {
        swap(&arr[1], &arr[i]);
        heapify(arr, i - 1, 1);
    }
}

Time: O(n log n)
In-place, not stable

8. Visual: Insert 40

Before:
         50
       /    \
     40      20
    /  \
  10   30

After Insert 40 → Heapify Up:
         50
       /    \
     40      20
    /  \      \
  10   30      40

9. Applications of Binary Heaps

Application Use
Priority Queue Scheduling, Dijkstra
Heap Sort Sorting
Kth Largest/Smallest extractMax k times
Merge K Sorted Lists Min-Heap of heads
Median in Stream Max-Heap (lower) + Min-Heap (upper)
Huffman Coding Min-Heap for frequencies

10. Kth Largest Element

int findKthLargest(int arr[], int n, int k) {
    int heap[100], size = 0;
    for (int i = 0; i < n; i++) {
        insert(heap, &size, arr[i]);
        if (size > k)
            extractMax(heap, &size);
    }
    return heap[1];  // Root = kth largest
}

Time: O(n log k)

11. Comparison: Heap vs Array vs BST

Structure Insert Extract Search Space
Heap O(log n) O(log n) O(n) O(n)
Sorted Array O(n) O(1) O(log n) O(n)
BST (balanced) O(log n) O(log n) O(log n) O(n)

Heap wins for Priority Queue

12. Heap vs Priority Queue

Feature Heap Priority Queue
Structure Array-based complete tree Abstract
Implementation Binary Heap Can be heap, BST, etc.
Use Data structure ADT

Priority Queue is often implemented using Binary Heap

13. Summary Table

Feature Binary Heap
Type Complete Binary Tree
Property Max/Min Heap
Insert O(log n)
Extract O(log n)
Peek O(1)
Build O(n)
Best For Priority Queue, Scheduling

14. Practice Problems

  1. Implement Min-Heap
  2. Merge K sorted arrays
  3. Find running median
  4. K closest points to origin
  5. Heap Sort in descending order
  6. Check if array represents a heap

15. Key Takeaways

Insight
Binary Heap = Complete Tree + Heap Property
Array-based → Cache friendly
O(log n) insert/extract → Ideal for Priority Queue
buildHeap is O(n), not O(n log n)
Used in Dijkstra, Prim, Huffman, etc.

End of Notes

Last updated: Nov 12, 2025

Binary Heaps – Complete Notes

With C Code, Diagrams, Operations, and Applications

Binary Heaps – Complete Notes

With C Code, Diagrams, Operations, and Applications

Binary Heaps – Complete Notes

With C Code, Diagrams, Operations, and Applications

1. What is a Binary Heap?

Binary Heap is a complete binary tree that satisfies the heap property.

Two Types

Type Property
Max-Heap Parent ≥ Children
Min-Heap Parent ≤ Children

Complete Binary Tree

  • All levels filled except possibly the last
  • Last level filled left to right
         100
       /     \
     80       70
    /  \     /  \
  60   50   40   30

2. Array Representation

Root at index 1 (or 0)
For node at index i:
- Left Child: 2*i
- Right Child: 2*i + 1
- Parent: i/2

Max-Heap Array

Index:  1   2   3   4   5   6   7
      [100,80,70,60,50,40,30]

3. Heap Operations

Operation Time
insert() O(log n)
extractMax/Min() O(log n)
peek() O(1)
heapify() O(log n)
buildHeap() O(n)

4. Core Functions

A. Heapify (Down) – Maintain heap property

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;

    if (left <= n && arr[left] > arr[largest])
        largest = left;
    if (right <= n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

B. Insert

void insert(int arr[], int* n, int value) {
    (*n)++;
    arr[*n] = value;
    int i = *n;

    // Heapify Up
    while (i > 1 && arr[i] > arr[i/2]) {
        swap(&arr[i], &arr[i/2]);
        i = i / 2;
    }
}

C. Extract Max

int extractMax(int arr[], int* n) {
    if (*n == 0) return -1;

    int max = arr[1];
    arr[1] = arr[*n];
    (*n)--;

    heapify(arr, *n, 1);
    return max;
}

D. Build Heap from Array

void buildHeap(int arr[], int n) {
    for (int i = n / 2; i >= 1; i--)
        heapify(arr, n, i);
}

Time: O(n) (not O(n log n))

5. Full C Implementation (Max-Heap)

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;

    if (left <= n && arr[left] > arr[largest])
        largest = left;
    if (right <= n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void insert(int arr[], int* n, int value) {
    (*n)++;
    arr[*n] = value;
    int i = *n;
    while (i > 1 && arr[i] > arr[i/2]) {
        swap(&arr[i], &arr[i/2]);
        i /= 2;
    }
}

int extractMax(int arr[], int* n) {
    if (*n == 0) return -1;
    int max = arr[1];
    arr[1] = arr[*n];
    (*n)--;
    heapify(arr, *n, 1);
    return max;
}

void printHeap(int arr[], int n) {
    for (int i = 1; i <= n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int heap[100];
    int n = 0;

    insert(heap, &n, 10);
    insert(heap, &n, 30);
    insert(heap, &n, 20);
    insert(heap, &n, 50);
    insert(heap, &n, 40);

    printf("Max-Heap: ");
    printHeap(heap, n);  // 50 40 20 10 30

    printf("Extract Max: %d\n", extractMax(heap, &n));  // 50
    printf("After extract: ");
    printHeap(heap, n);  // 40 30 20 10

    return 0;
}

6. Min-Heap (Just Change Comparison)

// In heapify and insert, change > to <
if (left <= n && arr[left] < arr[smallest])  // Min-Heap

7. Heap Sort

void heapSort(int arr[], int n) {
    // Build max-heap
    for (int i = n / 2; i >= 1; i--)
        heapify(arr, n, i);

    // Extract max one by one
    for (int i = n; i > 1; i--) {
        swap(&arr[1], &arr[i]);
        heapify(arr, i - 1, 1);
    }
}

Time: O(n log n)
In-place, not stable

8. Visual: Insert 40

Before:
         50
       /    \
     40      20
    /  \
  10   30

After Insert 40 → Heapify Up:
         50
       /    \
     40      20
    /  \      \
  10   30      40

9. Applications of Binary Heaps

Application Use
Priority Queue Scheduling, Dijkstra
Heap Sort Sorting
Kth Largest/Smallest extractMax k times
Merge K Sorted Lists Min-Heap of heads
Median in Stream Max-Heap (lower) + Min-Heap (upper)
Huffman Coding Min-Heap for frequencies

10. Kth Largest Element

int findKthLargest(int arr[], int n, int k) {
    int heap[100], size = 0;
    for (int i = 0; i < n; i++) {
        insert(heap, &size, arr[i]);
        if (size > k)
            extractMax(heap, &size);
    }
    return heap[1];  // Root = kth largest
}

Time: O(n log k)

11. Comparison: Heap vs Array vs BST

Structure Insert Extract Search Space
Heap O(log n) O(log n) O(n) O(n)
Sorted Array O(n) O(1) O(log n) O(n)
BST (balanced) O(log n) O(log n) O(log n) O(n)

Heap wins for Priority Queue

12. Heap vs Priority Queue

Feature Heap Priority Queue
Structure Array-based complete tree Abstract
Implementation Binary Heap Can be heap, BST, etc.
Use Data structure ADT

Priority Queue is often implemented using Binary Heap

13. Summary Table

Feature Binary Heap
Type Complete Binary Tree
Property Max/Min Heap
Insert O(log n)
Extract O(log n)
Peek O(1)
Build O(n)
Best For Priority Queue, Scheduling

14. Practice Problems

  1. Implement Min-Heap
  2. Merge K sorted arrays
  3. Find running median
  4. K closest points to origin
  5. Heap Sort in descending order
  6. Check if array represents a heap

15. Key Takeaways

Insight
Binary Heap = Complete Tree + Heap Property
Array-based → Cache friendly
O(log n) insert/extract → Ideal for Priority Queue
buildHeap is O(n), not O(n log n)
Used in Dijkstra, Prim, Huffman, etc.

End of Notes

Last updated: Nov 12, 2025