堆排序——C++实现

堆是完全二叉树的结构，因此对于一个有n个节点的堆，高度为O(logn)，二叉堆是采用数组的方式来存储的，分为大顶堆和小顶堆两种：
大顶堆：根节点大于等于自己的两个孩子节点。

小顶堆：根节点小于等于自己的两个孩子节点。

堆排序总共分为两步：
1、初始化建堆：
找到一个树的最后一个非叶节点， 计算公式为 (n-1)/2 -1， 然后遍历树的每个非叶节点，使其符合堆的规则。

2、排序重建堆：
将堆的顶部，与最后一个元素交换，然后将数组长度减一，将剩下的元素重新建成一个堆。

时间复杂度：初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)。

空间复杂度：O(1)。

代码如下：

#include <iostream>
using namespace std;

void adjust_heap(int arr[], int root, int length){
        int left = 2*root + 1;
        int right = 2*root + 2;
        int max = root;
        if( left < length && arr[left] > arr[max])
                max = left;
        if( right < length && arr[right] > arr[max])
                max = right;
        if(max != root){
                swap( arr[max], arr[root]);
                adjust_heap(arr, max, length);
        }
}

void heap_sort(int* arr, int len){
		//初始化建堆：
        for(int i = len/2 -1; i >= 0; --i)
                adjust_heap(arr, i, len);
         //排序重建堆     
        for(int i = len - 1; i >= 0; i--){
                swap(arr[0], arr[i]);           //堆顶元素和末尾元素进行交换
                adjust_heap(arr, 0 , i);        // 对顶点进行一次堆排序
        }
}

int main(){
        int a[10] = {3, 2, 7, 4, 2, -999, -21, 99, 0, 9  };
        int len= sizeof(a) / sizeof(int);

        for(int i = 0; i < len; ++i)
                cout << a[i] << ' ';
        cout << endl;

        heap_sort(a, len);

        for(int i = 0; i < len; ++i)
                cout << a[i] << ' ';
        cout << endl;

        return 0;
}

参考：https://blog.csdn.net/pursue_my_life/article/details/80253469
https://blog.csdn.net/m0_37907797/article/details/102636859