1. 堆
1.1 简介
堆又称二叉堆（由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆），在结构上可以视为一棵完全的二叉树（不过堆又增加了最大堆和最小堆的性质，下边1.2会讲）。完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素：
Parent = floor((i-1)/2)，i 的父节点下标
Left = 2i + 1，i 的左子节点下标
Right = 2i+ 2，i 的右子节点下标
n/2-1以及之前的都是父节点
1.2 二叉堆一般分为两种：最大堆和最小堆：
- 最大堆：
最大堆中的最大元素值出现在根结点（堆顶）
堆中每个父节点的元素值都大于等于其孩子结点（如果存在）
- 最小堆：
最小堆中的最小元素值出现在根结点（堆顶）
堆中每个父节点的元素值都小于等于其孩子结点（如果存在）
2. 堆排序
堆排序主要分三步：
（1）.构建堆
（2）.调整堆
（3）.堆排序
具体步骤：
- 1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆：从最后一个父节点开始（向前），将所有父节点都跟它的子节点比较，保证所有父节点大于子节点。
- 2.将根节点与尾节点交换并输出此时的尾节点
- 3.将剩余的n -1个节点重新进行堆有序化，此时因为只有堆顶的数据是新换上来的，只需要它跟它的子节点比较，因为只有最上边的是新换上来的，所以只需要跟子节点比较，一直往下沉即可。
- 4.重复步骤2，步骤3直至构造成一个有序序列
首先需要明确一点，构建堆是在数组基础上构建的，换句话说就是将数组抽象成一个二叉堆，而不需要另构建。
在构建堆之前需要保证一点，构建之后的结构需要堆序性质。
代码：
void swapValue(int *arr, int i, int j)
{
if (arr==NULL) {
return;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//对index所在的节点，判断是否有子节点，如果有则比较，并交换，保证该节点比子节点都大。如果产生交换了，则交换下去的节点还需要和它的节点做同样的判断交换。
void maxHeapify(int *arr, int index, int len)
{
if (arr==NULL || len<=0) {
return;
}
int left = 2*index+1;//因为是二叉堆，满足完全二叉树的结构，所以只判断左子树就知道有无，子节点了
int right = left+1;
int max = left;
while (left < len) {//证明有子节点
if (right<len && arr[right]>arr[left]) {
max = right;
}
if (arr[max]>arr[index]) {
swapValue(arr, max, index);
}
index = max;
left = 2*index+1;
right = left+1;
max = left;
}
}
//算法堆排序：代码是升序
void heapSort(int *arr, int len)
{
if (arr==NULL || len<=0) {
return;
}
//1.构建堆(数组数据满足堆序)
for (int i=len/2-1; i>=0; i--) {
maxHeapify(arr, i, len);
}
swapValue(arr, 0, len-1);//2.首尾交换
len--;
while (len>1) {
maxHeapify(arr, 0, len);//3.重新调整堆（满足大顶堆），因为只有最上边的是新换上来的，所以只需要跟子节点比较，一直往下沉即可
swapValue(arr, 0, len-1);//4.首尾交换
len--;
}
}
