Max Heap

Definition

complete binary tree + max tree

Functions

Delete Max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int remove_largest(vector<int>& heap) {
    if(heap.empty()){
        throw std::runtime_error("Heap is empty");
    }

    int result = heap[0];
    heap[0] = heap.back();// returns a reference to the last element in the vector. 
    heap.pop_back();
    int cursor = 0;
    int size = heap.size();
    while(true){
        int left = 2 * cursor + 1;
        int right = 2 * cursor + 2;
        int largest_index = cursor;
        
        if(left < size && heap[left] > heap[largest_index]){
            largest_index = left;
        }
        if(right < size && heap[right] > heap[largest_index]){
            largest_index = right;
        }
        if(largest_index == cursor){
            break;
        }
        std::swap(heap[cursor], heap[largest_index]);
        cursor = largest_index;
    }
    return result;
}

Insert

1
2
3
4
5
6
7
8
9
10
11
12
void insert(vector<int>& heap, int value){
    heap.push_back(value);
    int cursor = heap.size() - 1;
    while(cursor > 0){// comparing with parent, so cursor = 0 is not needed
        int parent = (cursor - 1) / 2;
        if(heap[cursor] > heap[parent]){
            std::swap(heap[cursor], heap[parent]);
            cursor = parent;
        }
        else break;
    }
}

heapify

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void heapify(vector<int>& arr, int n, int i){
    int largest = i, left = 2 * i + 1, right = 2 * i + 2;
    
    if(left < n && arr[left] > arr[largest]){
        largest = left;
    }
    if(right < n && arr[right] > arr[largest]){
        largest = right;
    }

    // recursively heapify the affected sub-tree
    if(largest != i){
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

heap sort

1
2
3
4
5
6
7
8
9
10
11
12
13
void heap_sort(vector<int> &arr){
    // build the max heap first
    int n = arr.size();
    for(int i = n / 2 - 1; i >= 0; i--){
        heapify(arr, n, i);
    }

    // extract elements from the heap
    for(int i = n - 1; i > 0; i--){
        std::swap(arr[0], arr[i]);// move the largest to the end
        heapify(arr, i, 0);// heapify the rest for extraction in the next iteration
    }
}

Example:

If you heapify [4, 10, 3, 5, 1], the max heap becomes:

1
[10, 5, 3, 4, 1]

This is a max heap, but not a sorted array.

  • Swap root with last: [1, 5, 3, 4, 10] → now 10 is in final place.

  • Heapify first 4: [5, 4, 3, 1, 10].

  • Swap root with last of heap: [1, 4, 3, 5, 10].

  • Heapify first 3: [4, 1, 3, 5, 10].

  • Swap root with last of heap: [3, 1, 4, 5, 10].

  • Heapify first 2: [3, 1, 4, 5, 10] → root = 3.

  • Swap root with last: [1, 3, 4, 5, 10].

Final result: [1, 3, 4, 5, 10] ✅ sorted!

Complexity:

  • Time: O(n log n)