堆与堆排序

堆

堆是具有下列性质的完全二叉树：
每个节点的值都大于或等于左右孩子节点的值，称为大顶堆；
每个节点的值都小于或等于左右孩子节点的值，称为小顶堆。

堆排序

堆排序的思想是首先构建一个大顶堆（从小到大排列）,然后将根节点的值移除，该根节点值就是序列最大值，然后重建调整成一个大顶堆，再次将根节点移除，该根节点即为第二大值，循环往复，就能形成一个有序序列了。
代码实现：

#include <iostream>

using namespace std;

void adustHeap(int* arr, int low, int high) {
    int big = arr[low];
    for(int i = 2*low + 1; i <= high; i = 2*i + 1){
        if((i < high) && (arr[i] < arr[i+1]))
            ++i;
        if(big > arr[i])
            break;
        arr[low] = arr[i];
        low = i;
    }
    arr[low] = big;
}

void heap_sort(int* arr, int length){
    if(arr == NULL || length <= 0) {
        return;
    }
    for(int i = length/2 - 1; i >= 0; --i){
        adustHeap(arr, i, length-1);
    }
    for(int j = length-1; j > 0; --j){
        swap(arr[0], arr[j]);
        adustHeap(arr, 0, j-1);
    }
}
int main() {
    int arr[10] = {8, 3, 9, 0, 2, 4, 6, 1, 7, 5};
    heap_sort(arr, 10);
    for(int i = 0; i < 10; ++i)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}