目录
一、建堆
二、利用堆删除思想来进行排序
三、堆排序的时间复杂度
一、建堆
- 升序：建大堆
- 降序：建小堆
建堆方式：
向上调整建堆：模拟的是插入数据的过程
//排升序建大堆
void HeapSort(int* a, int n)
{//建大堆for (int i = 1; i < n; i++){AdjustUp(a, i);}
}
向下调整建堆（左右子树必须是大堆或小堆（插入之前得是堆））：
void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0;--i)//先找到最后一个非叶子结点即上图的6 n-1是最后一个数据的下标，再-1除以2就是父节点{AdjustDown(a, n, i);}
}注：向下建堆的效率O（N）比向上建堆的效率O（N*logN）高
数学证明如下：
二、利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
三、堆排序的时间复杂度
所以如果用来排序的话，无论是向上调整还是向下调整建堆，总的时间复杂度都是O(N*logN)
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<assert.h>typedef int HPDataType;
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//先默认左孩子大while (child < n){//选出左右孩子中大的那一个 右孩子和左孩子的关系：大一if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//O(n*logn)
//排升序建大堆
void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; --i)//n-1是最后一个数据的下标，再-1除以2就是父节点{AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
int main()
{printf("调整前:");int a[10] = { 2,1,5,7,6,8,0,9,3 };for (int i=0;i<9;i++){printf("%d ", a[i]);}printf("\n");HeapSort(a, 9);printf("调整后:");for (int i = 0; i < 9; i++){printf("%d ", a[i]);}return 0;
} 
