Heapsort in C++

Below is an example of the Heapsort algorithm in C++. See the Heapsort page for more information and implementations.


heapsort in C++

#include <iostream>
#include <vector>

// to heapify a subtree rooted with node i which is an index in array[]
void heapify(std::vector<int> &arr, int size, int i) {
    int max = i; // initialize max as root
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // if left child is larger than root
    if (left < size && arr[left] > arr[max])
        max = left;

    // if right child is larger than max
    if (right < size && arr[right] > arr[max])
        max = right;

    // if max is not root
    if (max != i) {
        // swap
        int temp = arr[i];
        arr[i] = arr[max];
        arr[max] = temp;

        // recursively heapify the affected sub-tree
        heapify(arr, size, max);
    }
}

void heapSort(std::vector<int> &arr) {
    int size = arr.size();

    // build heapSort (rearrange array)
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(arr, size, i);
    }

    // one by one extract an element from heapSort
    for (int i = size - 1; i >= 0; i--) {
        // move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // call max heapify on the reduced heapSort
        heapify(arr, i, 0);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    heapSort(arr);
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}

Discussion