1. /*
    2.     堆排序：我们可以将堆分为大根堆与小根堆其特性是根节点均大于左右孩子结点（大根堆），或根节点均小于左右孩子结点
    3.             这样我们便可以每次输出根节点，再把最后一个元素放到堆顶，进而重新构造一个堆
    4. */
    5. #include <stdio.h>
    6. void swap(int &a, int &b) {//交换函数
    7.     int tmp;
    8.     tmp = a;
    9.     a = b;
    10.     b = tmp;
    11. }
    12. void heapAdjust(int *arr,int k, int len) {//堆的调整,将传入的以k为根节点的子树调整为大根堆
    13.     arr[0] = arr[k];//暂存arr[k]
    14.     for (int i = 2 * k; i <= len;i*=2) {
    15.         if (i < len&&arr[i] < arr[i + 1])//如果右孩子更大，i指向右孩子
    16.             i++;
    17.         if (arr[0] >= arr[i]) break;
    18.         else {
    19.             arr[k] = arr[i];
    20.             k = i;//继续向下调整
    21.         }
    22.     }
    23.     arr[k] = arr[0];
    24. }
    25. void buildMaxHeap(int *arr,int len) {//初始建堆
    26.     for (int i = len / 2; i > 0;i--) {
    27.         heapAdjust(arr,i,len);
    28.     }
    29. }
    30. void heapSort(int *arr, int len) {
    31.     buildMaxHeap(arr,len);//建堆
    32.     for (int i = len; i >= 1;i--) {
    33.         printf("%d ",arr[1]);
    34.         swap(arr[i],arr[1]);//堆底弄上去
    35.         heapAdjust(arr,1,i-1);//把剩余的元素排成堆
    36.     }
    37. }
    38. int main() {
    39.     int arr[] = { 0,9,3,4,10 };
    40.     heapSort(arr,4);
    41.     return 0;
    42. }