堆排序实现代码

构建最小堆

#include 
using namespace std;

const int N = 1e5 + 10;
int arr[N];

void adjust(int a[], int n, int i){
    int mi = i, l = i * 2 + 1, r = i * 2 + 2;
    if(l < n && a[mi] > a[l]) mi = l;
    if(r < n && a[mi] > a[r]) mi = r;
    if(mi != i){
        swap(a[mi], a[i]);
        adjust(a, n, mi);
    }
}

void buildMinHeap(int a[], int n){
    for(int i = n / 2 - 1; i >= 0; i--){
        adjust(a, n, i);
    }
    for(int i = n - 1; i >= 0; i--){
        swap(a[0], a[i]);
        adjust(a, i, 0);
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    buildMinHeap(arr, n);
    return 0;
}

构建最大堆

#include 
using namespace std;

const int N = 1e5 + 10;
int arr[N];

void adjust(int a[], int n, int i){
    int ma = i, l = i * 2 + 1, r = i * 2 + 2;
    if(l < n && a[ma] < a[l]) ma = l;
    if(r < n && a[ma] < a[r]) ma = r;
    if(ma != i){
        swap(a[ma], a[i]);
        adjust(a, n, ma);
    }
}

void buildMinHeap(int a[], int n){
    for(int i = n / 2 - 1; i >= 0; i--){
        adjust(a, n, i);
    }
    for(int i = n - 1; i >= 0; i--){
        swap(a[0], a[i]);
        adjust(a, i, 0);
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    buildMinHeap(arr, n);
    return 0;
}