各位读者，大家好。 因为算法和数据结构相关的知识都是在国外学的，所以有些词汇翻译的可能不准确，然后一些源代码的注释可能是英文的，如有给大家带来什么不方便，请见谅。今天我想写一下Heap相关的知识，从基本的结构到最后的一些常用functions. Heap 的数据结构其实可以看成Array, 例如a[] = {5,3,6,8,2,1,0}这个数组， 我们可以将其看作如下的结构：
Heap又可以分成2种类型：Max-Heap 和 Min-Heap。 Max-Heap的意思是每一个node的key值都要大于它的children的key值；反之Min-Heap的的结构是每个node的key值都小于它的children的key值。 例如一个Max-Heap的结构如下：
对于以上的Heap 数据结构的分析，可以分析出对于一个含有N个元素的heap或者称之为array，其heap的结构的的高度（level）是1+logN. 例如上面的结构就是1+log7 = 3 层。
如果一个heap当中只有一个element破坏了Max-heap/Min-Heap structure的结构，那么如果希望重构这个heap让其重新维持Max/Min的话，这个element需要跟它的children中的较大的值交换，一直交换到它的children都小于它的key值为止，这个过程最多进行这个tree的高度次（即：the height of tree）， 而这个height就是O(logN)。我们称这个过程为Max-Heapify或者Min-Heapify。以下展示的是C++的代码来实现Max-heapify的过程， 如下：
/*
heapify() function is used to keep the heap structure as max/min heap. If there is a node voilate the max/min heap, this function will try to correct it and restructure it still keep the max/min heap property. parameter: 1. a[], the array
2. i; where the node violate the max/min heap
3. n; the numbers of the a[]; return: void */
void heapify(int a[], int i, int n){ int j, temp;
j = *i;//the node i's left node if (j >= n){//i is the leaf of the tree return;
} temp = a[i]; while (j < n) {//i is not the leaf if (a[j]<a[j+]) {//left child is less than right child j = j + ;
} if (temp>a[j]) { break;
} if (temp <= a[j]) {// if node i violate the structure, exchange the values. a[j/] = a[j];
a[j] = temp;
j = j * ;
} }
}
以上的代码展示的是max-heapify 的过程， 那么如何将一个乱续的heap或者array重构成一个max-heap或者min-heap呢？其实有了以上的功能，将一个完全杂乱的heap装换成max-heap就很简单了。我们只需要从倒数第二层的最左边的一个element开始一直向上面的level的nodes做Max-heapify的过程utill to the root of the tree, 最后就一定能将整个heap转化成Max-Heap. 倒数第二层的最左边的一个element的index是N/2 - 1; 这中间的整个过程如下所示：
将整个unsorted heap转化成Max-Heap的过程的时间复杂度Efficiency = O(N), 而不是O(LogN); 这个复杂度的推导过程下次再跟大家解释，是通过数学运算推导出来的，这里就不详细解释了。其实这个代码很简单，他的C++的实现代码如下：
/* buildMaxHeap functions is used to force and restructure the heap to an maximum heap structure
parameters: 1: a[];
2: n;// the number of the arrary return void
*/ void buildMaxHeap(int a[], int n){ for (int i = n/-; i >= ; i --) { heapify(a, i, n);
} }
进过以上的过程，我们知道了如何将一个无序的heap或者array转换成Max-Heap, 那么接下来我们就解释一下如何将获得的Max-heap进行排序，它主要经过一下几个过程：
1. 交换heap的最后一个key a[N]和heap的root的key a[1]; 此时a[1]破坏了Max-heap的structure，a[N]是最大值。
2. 我们对除了最后几个已经交换过值的elements剩下的tree进行heapfy的过程；//假如从[j.....N]的elements是之前比较过的，那么就只对[1......j-1]进行heapify的过程。
其具体的c++代码的实现过程如下所示：
/*
heapSort function is to sort the heap in an descending or ascending order parameter:
1, a[], //the array
2, n,// how many nodes should be checked in the heapify function, actuall here is not all the node should be checked return void */ void heapSort(int a[], int n){ int temp; for (int i = n-; i >= ; i --) {//the last indices of array is n-1, loop until to the root temp = a[];
a[] = a[i];
a[i] = temp; heapify(a, , i-);
}
}
综合以上的不做，我们已经可以完成对一个完全无序的array或者heap进行heap-sort的过程，它的时间复杂度如下：
Efficiency = O(N)+O(1)+O(N*logN) = O(N*logN);
那么heap的总结就结束了，下周准备写一些Binary Search Tree （BST）的知识。
如果有什么错误的地方，欢迎大家留言指正，谢谢。