堆
堆是具有下列性质的完全二叉树：
每个节点的值都大于或等于左右孩子节点的值，称为大顶堆；
每个节点的值都小于或等于左右孩子节点的值，称为小顶堆。
堆排序
堆排序的思想是首先构建一个大顶堆（从小到大排列）,然后将根节点的值移除，该根节点值就是序列最大值，然后重建调整成一个大顶堆，再次将根节点移除，该根节点即为第二大值，循环往复，就能形成一个有序序列了。
代码实现：
#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;
}
