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

Implement Min-Heap
Merge K sorted arrays
Find running median
K closest points to origin
Heap Sort in descending order
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