在堆排序算法中，应用的是最大堆，最小堆通常用于结构优先队列。
堆的数据结构
如果咱们应用指针来示意堆有序的二叉树，那么每个元素都须要3个指针来找到它的高低结点（父结点和两个子节点各须要一个）。但如果应用齐全二叉树来示意二叉堆，则只须要数组而不须要指针皆能够示意。具体方法就是将二叉树的结点依照层级程序放入数组中，根结点在地位1[不应用数组的第一个地位0]。则结点k的父结点为k/2，两个子结点地位为k*2、k*2+1。
高级实现
- 数组实现（无序）insert和栈的push()操作统一；del须要增加一段相似于抉择排序的内循环找到最大元素并删除
- 数组实现（有序）insert须要将所有较大元素向右挪动以使数组放弃有序；del和栈的pop()操作统一
上述两种高级计划中，插入元素和删除最大元素这两个操作之一在最坏状况下须要线性工夫来实现。
应用无序序列是解决问题的惰性办法，仅在必要的时候才会采取行动（找到最大元素）；应用有序序列则是解决问题的踊跃办法，因为会尽可能防患未然（在插入元素时就放弃列表有序），使后序操作更高效。
堆的有序化
上浮：如果堆的有序状态因为某个结点变得比它的父结点更大而突破，那么就须要通过替换它和它的父结点来修复堆。
void swim(int nums[], int k, int n) { while (k > 1 && nums[k / 2] < nums[k]) { swap(nums[k / 2], nums[k]); k = k / 2; }}下沉：如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被突破了，那么就须要通过将它和它的两个子结点中的较大者替换来修复堆。
void sink(int nums[], int k, int n) { while (k * 2 <= n) { int j = k * 2; if (j < n && nums[j] < nums[j + 1]) j++; if (!(nums[k] < nums[j])) break; swap(nums[k], nums[j]); k = j; }}构建堆
堆排序之前首先须要将N个元素的数组结构一个堆。当然能够在O(NlogN)工夫内，从左至右遍历数组，用swim()保障左侧的元素曾经堆有序。更高效的方法是从右至左用sink()办法结构子堆。因为当用数组示意存储n个元素的堆时，叶结点下标别离是n/2 + 1, n/2 + 2, ... , n。每个叶结点都能够看成是只蕴含一个元素的堆。故这部分曾经堆有序，咱们只须要从n/2开始往前遍历一半元素，调用sink()，直到下标1即可。工夫复杂度为O(NlogN)。
for (int k = n / 2; k >= 1; k--) { sink(nums, k, n);}堆排序
构建完最大堆之后，将堆中的最大元素删除，而后放入堆放大后数组中空出的地位。这个过程和抉择排序相似（依照降序取出所有元素），但所需的比拟要少得多，因为堆提供了一种从未排序局部找到最大元素的无效办法。
void heap_sort(int nums[], int n) { for (int k = n / 2; k >= 1; k--) { sink(nums, k, n); } while (n > 1) { swap(nums[1], nums[n--]); sink(nums, 1, n); }}堆排序不是稳固的；是原地排序；工夫复杂度为O(NlogN)，空间复杂度为O(1)。