堆排序

#include <iostream>
#define N 10
using namespace std;

int arr[N+1];
int count = 0;

void shiftUp(int k){
    while(arr[k/2] < arr[k] && k > 1){
        swap(arr[k/2], arr[k]);
        k /= 2;
    }
}

void insert(int v){
    if(count + 1 > N) return;
    arr[count + 1] = v;
    count++;
    shiftUp(count);
}

void shiftDown(int k){
    while(2 * k <= count){
        int j = 2 * k;
        if(j + 1 <= count && arr[j + 1] > arr[j]){
            j = j + 1;
        }
        if(arr[k] > arr[j]){
            break;
        }
        swap(arr[j], arr[k]);
        k = j;
    }
}

int popMax(){
    if (!count) return 0;
    int v = arr[1];
    swap(arr[1], arr[count]);
    count--;
    shiftDown(1);
    return v;
}

void heapSort1(int a[], int n){
    for (int i = 0; i < n; i++){
        insert(a[i]);
    }

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

void heapSort2(int a[], int n){
    for (int i = 1; i <= n; i++){
        arr[i] = a[i -1];
    }

    for(int i = n/2; i > 0; i--){
        shiftDown(i);
    }
    count = n;
    for (int i = n - 1; i >= 0; i--){
        a[i] = popMax();
    }
}

int main(){
    int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    heapSort2(a, N);
    for (int i = 0; i < N; i++){
        cout << a[i] << " ";
    }
    
    return 0;
}