堆：通常是一个可以被看做一棵完全二叉树的数组对象。实际中也通常用 数组 来实现。（下面也都是基于数组来进行讨论的） 堆的定义 完全二叉树要么是满二叉树，若不满，则在最后一层是从左往右依次补齐的。
堆可以分为：大根堆 和 小根堆两种。 大根堆指：在这棵完全二叉树中，任何一棵子树的最大值都在子树的头节点； 小根堆相反。
接下来就是堆排序的过程：（以大根堆为例） 1、首先来看一个函数 heapinsert：heapinsert(int arr[], int i)表示在一个大根堆末尾 i 处插入节点后，仍维持一个0~i 的大根堆。 根据大根堆的定义：所有子树都是头节点最大，所以我们可以知道：当在末尾插入一个节点时，需要与其所在子树的头节点进行比较，若插入节点大于头节点，则需要将两者进行交换；若发现交换后的头节点仍然小于目前子树的头节点，继续交换…直到小于所在子树小于头节点或者到顶了。很明显，插入数据后维持大根堆是一个数据不断上浮的过程。 另外需要补充：若已知一个完全二叉树的头节点在数组中的索引为index，那么可以直到其左、右子节点（若存在）的索引为：2 * index + 1 与 2 * index + 2。其父节点的索引为：(index - 1)/2。
接下来，依据这个函数可以很顺利地建立一个大根堆。从下标0开始不断插入数据（调用heapinsert函数），直到数组最后一个元素，最终可以形成一个大根堆。
//交换数组中两个位置的数 void swap(int arr[], int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } //heapinsert函数 void heapinsert(int arr[], int index) { while(arr[index] > arr[(index - 1)/2]) { swap(arr, index, (index - 1)/2); index = (index - 1)/2; } } //建立大根堆,其中len表示传入的数组的长度 void makeheap(int arr[], int len) { for(int i = 0; i < len; i++) { heapinsert(arr, i); } }2、接下来看另外一个函数heapify：heapify(int arr[], int index, int heapsize)表示大根堆中索引为 index 的值变小了，仍然维持大根堆的过程。 试想根据大根堆的定义，若其中一个节点的值变小了，仍要维持一个大根堆，我们需要考虑，该节点的左右子节点（若存在）是否比现在的头节点大，若子节点更大，我们就需要调整，然后循环这种比较，直到所变小的节点沉到最底部 或者 没有子节点比它更大的时候，我们就维持好了一个大根堆。
过程如下：
void heapify(int arr[], int index, int heapsize) { int left = index * 2 + 1; //计算出左儿子的索引 while(left < heapsize){ //左儿子没有超出界限 int largest = (left + 1) < heapsize && arr[left] < arr[left + 1] ? (left + 1) : left; //找左右儿子中值大的节点，首先要判断右儿子是否存在，若不存在直接返回左儿子 largest = arr[index] > arr[largest] ? index : largest; //将index处的值与两个儿子中较大的节点比较,找到最大值所在的索引 if(largest == index) break; //若本身最大了，表示已经维持好了大根堆 swap(arr, index, largest); index = largest; left = 2 * index + 1; } }至此我们已经知道了在大根堆中一个值变小后仍然维持大根堆的过程。 前面铺垫了这么长，重点的堆排序怎么做到呢？ 过程如下： 1、先建立一个大根堆； 2、将堆顶元素与最后一个元素互换，将heapsize - 1;（相当于头节点变小了，可以调用heapify函数维持大根堆） 3、维持heapsize - 1 大小的大根堆（即将最大元素换到最后，然后下次排序不考虑这个数了，只对堆中剩下的元素进行排序）。 4、循环2~3过程，直到所有元素排完。
void heapsort(int arr[], int len) { makeheap(arr, len); for(int i = len - 1; i >= 0; i--) { swap(arr, 0, i); heapify(arr, 0, i); } } int main() { int array[7] = {1,5,7,3,9,11,15}; int len = sizeof(array)/sizeof(array[0]); heapsort(array, len); for(int i = 0; i < len; i++) { cout << array[i] << " "; } }至此，整个堆排序就完成了，相信经过这一整个流程，大家会对堆排序有更深的理解了。
