Heap Sort - Max Heap

#include <iostream>
#include <chrono>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

vector<int> randomVector(int n) {
    vector<int> vec(n);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        vec[i] = rand() % 100;
    }
    return vec;
}

void checkSort(vector<int>& a, int n) {
    int i;
    bool sorted = true;
    for (i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            sorted = false;
        }
        if (!sorted) {
            break;
        }
    }
    if (sorted) {
        cout << "정렬 완료.\n";
    }
    else {
        cout << "정렬 오류.\n";
    }
}

void heapify(vector<int>& a, int index, int n) {
    int leftChildIndex = 2 * index + 1;
    int rightChildIndex = 2 * index + 2;
    int largestIndex = index;
    if ((leftChildIndex < n) && (a[leftChildIndex] > a[largestIndex])) {
        largestIndex = leftChildIndex;
    }
    if ((rightChildIndex < n) && (a[rightChildIndex] > a[largestIndex])) {
        largestIndex = rightChildIndex;
    }
    if (largestIndex != index) {
        swap(a[index],a[largestIndex]);
        heapify(a, largestIndex, n);
    }

}

void buildMaxHeap(vector<int>& a, int n) {
    int i;
    for (i = n / 2; i >= 0; i--) {
        heapify(a, i, n);
    }
}


void heapSort(vector<int>& a, int n) {
    buildMaxHeap(a,n);

    for (int i = n - 1; i >= 1; i--) {
        swap(a[0], a[i]);
        heapify(a, 0, i);
    }
}

int main() {
    int n = 10;
    vector<int> vec = randomVector(n);
    cout << "Random Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " ";
    }
    auto start = chrono::high_resolution_clock::now();
    heapSort(vec, n);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    cout << "\nSorted Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
    checkSort(vec, n);
    cout << "Runtime: " << duration.count() << " seconds." << endl;
    return 0;
}

Heap Sort - Min Heap

#include <iostream>
#include <chrono>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

vector<int> randomVector(int n) {
    vector<int> vec(n);
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        vec[i] = rand() % 100;
    }
    return vec;
}

void checkSort(vector<int>& a, int n) {
    int i;
    bool sorted = true;
    for (i = 0; i < n - 1; i++) {
        if (a[i] < a[i + 1]) {
            sorted = false;
        }
        if (!sorted) {
            break;
        }
    }
    if (sorted) {
        cout << "정렬 완료.\n";
    }
    else {
        cout << "정렬 오류.\n";
    }
}

void heapify(vector<int>& a, int index, int n) {
    int leftChildIndex = 2 * index + 1;
    int rightChildIndex = 2 * index + 2;
    int largestIndex = index;
    if ((leftChildIndex < n) && (a[leftChildIndex] < a[largestIndex])) {
        largestIndex = leftChildIndex;
    }
    if ((rightChildIndex < n) && (a[rightChildIndex] < a[largestIndex])) {
        largestIndex = rightChildIndex;
    }
    if (largestIndex != index) {
        swap(a[index], a[largestIndex]);
        heapify(a, largestIndex, n);
    }
}

void buildMinHeap(vector<int>& a, int n) {
    int i;
    for (i = n / 2; i >= 0; i--) {
        heapify(a, i, n);
    }
}


void heapSort(vector<int>& a, int n) {
    buildMinHeap(a, n);

    for (int i = n - 1; i >= 1; i--) {
        swap(a[0], a[i]);
        heapify(a, 0, i);
    }
}

int main() {
    int n = 10;
    vector<int> vec = randomVector(n);
    cout << "Random Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " ";
    }
    auto start = chrono::high_resolution_clock::now();
    heapSort(vec, n);
    auto end = chrono::high_resolution_clock::now();
    chrono::duration<double> duration = end - start;
    cout << "\nSorted Vector: ";
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " ";
    }
    cout << endl;
    checkSort(vec, n);
    cout << "Runtime: " << duration.count() << " seconds." << endl;
    return 0;
}