堆：一种数据结构，有最大堆和最小堆两种类型，实质上是一个完全二叉树，如果是最大堆，则父节点上的值比子节点上的值大，反之则是最小堆。
ps：这里提及的堆与常说的堆内存区域的堆不一样，此处提及的堆是一种简单的数据结构，而堆内存的实现较复杂。
堆排序：堆排序是一种比较高效的排序方式，时间效率为N*lgN，它利用最大堆的特性完成排序
本人之前的博文中有提到归并排序，与堆排序相比，二者效率相同，但堆排序还有个最大的好处就是，它比较省空间，在归并排序中需要申请额外左右数组空间，内存占用空间大。
堆排序分为三个步骤：
- 创建最大堆
- 确保最大堆中父节点的值比子节点的值都大
- 将根节点与最后一个叶子节点比较，择其大者剔除出堆，再重复第2、3步。
第二步是整个堆排序的关键。
public static void maxHeapify(int[] array, int heapsize, int i){
int l = 2*i + 1;
int r = 2*i + 2;
int large = i;
if (l < heapsize && array[i] < array[l]) {
large = l;
}else {
large = i;
}
if (r < heapsize && array[large] < array[r]) {
large = r;
}
if (large != i) {
int temp = array[i];
array[i] = array[large];
array[large] = temp;
//因为将最大值和父节点交换了位置，新的子节点并不能保证一定是比它的子节点大
//所以需要递归，确定交换的子节点比它的子节点都大
//而没有动的子节点是不需要进行递归的，因为它的数值没有变，如果之前满足最大堆条件，现在就还是满足的
maxHeapify(array, heapsize, large);
}
}
maxHeapify过程并不复杂，注意到函数中有参数heapsize，本例中的堆其实是基于数组的，堆大小并不一定等于数组长度的，因为在堆排序的第三步中需要将堆的根节点剔除出堆，所以堆的长度一直在变。
创建最大堆过程：
public static void buildMaxHeap(int[] array){
int heapsize = array.length;
for (int i = heapsize/2; i >= 0; i--) {
maxHeapify(array,heapsize,i);
}
}
buildMaxHeap过程，有两点需要注意。
- 堆其实是一个完全二叉树，且是以数组实现的，那么二叉树中i节点的左子节点一定是2i + 1，右子节点一定是2i + 2，对应在数组中 array.length/2 到 array.length - 1之间的节点，肯定是叶子节点，没有子节点，因为如果有子节点，则子节点的索引已经大于数组长度了，所以不可能出现。
- 创建堆必须逆序，即必须先确认完全二叉树底层的节点具有最大堆的性质，父节点必须大于子节点，然后再逐层往上，最后才确保根结点具有最大堆性质才行。如果遍历是从0开始，那么整个完全二叉树将不具有最大堆性质。
buildMaxHeap后，完全二叉树中的根结点就一定是整个数组中最大的（因为父节点一定大于子结点的性质）。注意，只能保证根结点的值是最大的，最下方的最后的子结点，则并不一定是最小的值。
heapSort过程，因为知道根结点一定是最大的，所以可以将根结点和数组中最后一位相比较，交换二者的值，然后再将数组中最后一位剔除出堆（此时，数组中最后一位已经是最大值了），再重新确保最大堆特性，持续这个过程，即将完全堆排序。
public static void heapSort(int[] array){
int heapsize = array.length;
for (int i = heapsize - 1; i > 0; i--) {
if (array[i] < array[0]) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
heapsize --;
maxHeapify(array, heapsize, 0);
}
}
}
测试代码：
public static void main(String[] args) {
int[] array = {4,1,3,2,16,9,10,14,8,7,5};
buildMaxHeap(array);
print(array);
heapSort(array);
print(array);
}
堆排序的时间效率计算较为复杂，主要是其中牵涉到递归。一般而言，算法的时间效率仅考虑最差极值情况。maxHeapify过程，根结点的值最小，那么需要将根结点的值一直往树的下层挪，最后根结点的值将变成叶子结点的值，那么挪动的距离则为二叉树的高度，于是maxHeapify的效率与二叉树的高度相关，二叉树的高度为lgN，那么maxHeapify的效率为lgN，在heapSort过程中，遍历N次，每次效率均为lgN，那么整个排序算法的效率为N*lgN。
ps：以上是本人的简单推测算法，详细推算请参考算法导论。
优先队列是一种用来维护由一组元素构成的集合S的数据结构，内部数据排序位置由元素本身决定，通常优先队列首位数据是集合中最大的或最小的一位。
优先队列中首位数据是最大值，则称为最大优先队列。
最大优先队列只是首位最大，并不保证队列中均是由大到小顺序排列。如果是以数组实现，则可保证，但此处是以堆实现，则不能确保从大到小排列，只能保证首位值最大。
优先队列有常见三个操作：
- 获取最大值
- 获取最大值并将值删除出堆
- 更改某个位置值大小
heapMaxNum过程非常简单：
public static int heapMaxNum(int[] array){
return array[0];
}
heapExtractMax：
public static int heapExtractMax(int[] array){
if (array.length == 0) {
System.out.println("heap is empty");
}
int i = array.length - 1;
int max = array[0];
array[0] = array[i];
maxHeapify(array, array.length - 1, 0);
return max;
}
heapExtractMax过程，取出最大值，然后将堆中最后一位放到首位，再执行maxHeapify，检查最大堆性质。
heapIncreaseKey：
public static void heapIncreaseKey(int[] array, int i, int key){
if (key < array[i]) {
System.out.println("the key is small than origin");
return;
}
array[i] = key;
int parent = getParent(i);
while (parent != Integer.MIN_VALUE && array[i] > array[parent]) {
int temp = array[i];
array[i] = array[parent];
array[parent] = temp;
i = parent;
parent = getParent(parent);
}
}
heapIncreaseKey过程，需要将当前值与父节点比较，如果大于父节点则交换位置，再从当前父节点往上，循环此过程。
因为父节点一定大于原节点，所以并不需要从原节点再往下循环，确保最大堆性质了。
根据完全二叉树性质，获取父节点代码如下：
public static int getParent(int i){
if (i == 0) {
return Integer.MIN_VALUE;
}else {
if (i%2 == 0) {
return (i-1)/2;
}else {
return i/2;
}
}
}
使用堆实现优先队列比用纯数组实现更高效，纯数组因为需要保证从大到小排列，则插入效率为N，而堆插入效率为N*lgN
ps：堆一定包含非常重要的属性，堆长度，本例中仅使用数组简单实现。
网友评论