数据结构堆二叉堆是一个数组它可以被看成一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素。除最底层外该树是完全充满的而且是从左向右充满。二叉堆可以分两种形式最大堆和最小堆。这两种堆中结点的值都要满足堆的性质。最大堆要满足除了根以外的所有结点都要满足所有的父结点都大于或等于他的子结点Arr[parent(i)]Arr[i]也就是说每个结点的值最多与其父结点一样大并且在任一子树中该子树包含的所有结点的值都不大于该子树根结点的值(如下图所示为一个最大堆。最小堆的组织方式正好相反最小堆是所有结点的值都大于或等于他的父结点的值Arr[parent(i)] Arr[i]在堆排序算法中我们使用的是最大堆。而最小堆通常用于构造优先队列。堆的维护我们先看使用伪代码写的max_heapify()的过程max_heapify(Arr[],i) lleft(i) //2i rright(i) //2i1 if lArr.size and Arr[l]Arr[i] largestl else largesti if rArr.size and Arr[r]Arr[largest] largestr if largest ! i exchange Arr[i] with Arr[largest] max_heapify(Arr,largest)max_heapify()是用于维护堆最大堆的重要过程他输入一个数组Arr和一个下标i。我们假定结点i的所有子结点都满足最大堆的性质只有i结点不满足最大堆的性质因为Arr[i]可能小于其孩子节点这样就违背了最大堆的性质。调用max_heapify()过程后能使结点i在最大堆中逐级下降从而使以下标i为根结点的子树重新遵守最大堆的性质。在图示a中Arr[2]违背了最大堆的性质。我们可以执行max_heapify(Arr2)来恢复堆的性质。在执行程序的每一步中从Arr[i]、Arr[left(i)]、Arr[right(i)]中选出最大的并将其下标储存在largest中。如果Arr[i]是最大的那么以i为根结点的子树已经是最大堆程序结束。否则最大元素是i的某个孩子节点则交换Arr[i]和Arr[largest]的值。在交换之后Arr[i]都会大于它两个孩子结点的值从而满足了最大堆的性质。在交换之后下标largest的结点是原来的Arr[largest]的值于是以该结点为根的子树又有可能会违反最大堆的性质。因此需要对孩子树递归调用max_heapify();维护堆的C语言代码void max_heapify(int arr[], int i, int size) { int largest; int l i * 2; int r (i * 2) 1; if (lsize arr[l]arr[i]){ largest l; } else { largest i; } if (rsize arr[r]arr[largest]) { largest r; } if (largest! i){ int temp arr[i]; arr[i] arr[largest]; arr[largest] temp; max_heapify(arr, largest, size); } }建堆我们可以用自顶向上的方法利用过程max_heapify把一个大小为nArr.length的数组Arr[1...n]转换为最大堆。不难证明Arr[(n/2)1...n]的元素都是页结点即他们没有子结点他们都可以看成只包含一个元素的堆。我们可以利用build_max_heapify过程对树中的其他结点都调用一次max_heapify。伪代码实现过程如下build_max_heapifyArr) for i(Arr.size)/2 downto 1 max_heapify(Arr,i)因此我们可以在线性时间内把一个无序素组构造成为一个最大堆。堆排序算法讲了那么久终于到重点了我要开始装逼了请大家拿好笔上面我们讲到我们建立了一个大顶堆大顶堆的的特点就是数组中最大的元素总是在Arr[1]中。我们可以把Arr[1]和Arr[n]互换让最大的元素和最后一个元素互换位置然后我们从堆中拿出最后一个元素也就是最大的元素。做法很简单我们只需要把数组的Arr.size属性减去1即可。在剩余的结点中只有一个元素不满足最大堆的性质那就是我们刚刚换上去的Arr[1]这时候我们只需要调用一次max_heapify(Arr,1)维护堆剩下的结点又编程了一个n-1的大顶堆了。这时我们又可以重新从Arr[1]取出最大值了然后一直重复这个过程就能得到一个排好序得数组了是不是感觉很简单伪代码实现过程heapsort(Arr) build_max_heap(Arr) //建立一个大顶堆 for iArr.length downto 2 exchange Arr[1] with Arr[i] Arr.lengthArr.length-1 max_heapify(Arr,1)总体测试代码#include iostream using namespace std; void max_heapify(int arr[], int i, int size) { int largest; int l i * 2; int r (i * 2) 1; if (l size arr[l] arr[i]) { largest l; } else { largest i; } if (r size arr[r] arr[largest]) { largest r; } if (largest ! i) { int temp arr[i]; arr[i] arr[largest]; arr[largest] temp; max_heapify(arr, largest, size); } } void build_max_heapify(int arr[], int size) { for (int i size / 2; i 1; i--) { max_heapify(arr, i, size); } } void sort_head(int Arr[], int size) { build_max_heapify(Arr, size); int len size; int temp; for (int i size; i 2; i--) { temp Arr[1]; Arr[1] Arr[i]; Arr[i] temp; max_heapify(Arr, 1, --len); } } int main() { int Arr[11] { 0,16,14,10,8,7,9,3,2,4,1 };//0号元素我们是不用得 sort_head(Arr, 10); //堆排序 for (int i 1; i 10; i) { cout i : Arr[i] endl; } return 0; }