堆和堆排序

堆：

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

堆排序

#include <iostream>
using namespace std;
/******************堆排序************************/
void AdjustHeap(int arr[], int s, int m) {
    int temp = arr[s];
    for(int j = 2*s+1; j <= m; j *= 2 + 1) {
        if(j < m && arr[j] < arr[j+1])
            j++;
        if(temp > arr[j])
            break;
        arr[s] = arr[j];
        s = j;
    }
    arr[s] = temp;
}
void HeapSort(int arr[], int length) {
    if(length <= 0)
        return;
    for(int i = length/2 -1; i >= 0; --i) {
        AdjustHeap(arr, i, length-1);
    }
    for(int i = length -1; i > 0; --i) {
        swap(arr[0], arr[i]);
        AdjustHeap(arr, 0, i-1);
    }
}