dataStructures/sort/HeapSort/MaxHeap.cpp

//
// Created by tangs on 2018/11/19.
//

#include <iostream>

using namespace std;

void AdjustDown(int A[], int k , int len) {
    A[0] = A[k];
    int i;
    for (i = 2 * k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i + 1]) {
            i++;
        }
        if (A[0] >= A[i]) {
            break;
        } else {
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = A[0];
}

void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i > 0; i--) {
        AdjustDown(A, i, len);
    }
}

void MaxHeapSort(int A[], int len) {
    BuildMaxHeap(A, len);
    int i;
    for (i = len; i > 1; i--) {
        swap(A[i], A[1]);
        AdjustDown(A, 1, i - 1);
    }
}

int main(){
    int A1[] = {6, 1, 5, 2, 1, 9, 10, 24, 7, 0};
    MaxHeapSort(A1, 9);

    // print:
    // 0 0 1 1 2 5 7 9 10 24
    for (int i = 0; i < 10; i++) {
        cout << A1[i] << " ";
    }
    cout << endl;
    return 0;
}