堆排序与大顶堆

(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)

假如，有一天，别人问到你，你了解堆排序吗？或者你对大顶堆了解吗？
之前问我的话，我是不太了解的，不过现在了解多了。
也期望通过下文，你也能对它了解起来。

关于堆排序

堆排序所采用的方式是：
首先初始构建一个大顶堆，然后再利用大顶堆的特点，来逐个找出最大的点；

这样的话，疑问来了，什么是大顶堆：
关于大顶堆，
首先，是一个完全二叉树的结构，并且是顺序存储的完全二叉树结构；
其次，每个根结点的值都大于或等于其左右孩子结点的值；

完全二叉树存储到数组

完全二叉结构，顺序存储是什么样子呢？
例如：父子节点关系
第一层：(n1)
第二层：n1->(n2), (n3)
第三层：n2->(n4), (n5), n3->(n6, n7)
第四层：n4->(n8), (n9), n5->(n10), (n11), n6->(n12), (n13), n7->(n14, n15)
…

对应节点：
第一层：n1
第二层：n2, n3
第三层：n4, n5, n6, n7
第四层：n8, n9, n10, n11, n12, n13, n14, n15
…

把完全二叉树，按照顺序逐层存储到数组中，就形成了[空位, n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12, n13, n14, n15…]这样一个数组；
因为采用了完全二叉树，所以呢，我们就能从数组中拎出这个二叉树出来：
假设数据arr[0]采用一个空位，arr[1]开始放这个完全二叉树

第一个节点arr[1]是root头节点
每个节点n的左叶子节点为arr[2n], 右节点为 arr[2n+1]

根节点值大于左右子节点

什么是根节点值大于子节点？
有了完全二叉树存储到数组的了解，我们再来看这个条件，根节点值大于子节点；
这个也就是字面的意思，头节点的值比较大，两个子节点随意，子节点没有大小关系；
所有节点，满足下面即可；
parent >= left child;
parent >= right child;
因为：left child 与 right child没有关系，可能存在left child比right child大很多的情况，或小很多的情况；
例如下面这种情况：
parent = 1000
left child = 999
left child-> left child = 900
left child -> right child = 800
right child = 9
right child-> left child = 6
right child -> right child = 7
但不论如何，parent始终大于自身的左右子节点，最终root节点是最大的。

大顶堆-使用它

有了堆大顶堆特点的了解，假设我们已经构造好了大顶锥，如何使用它获取最大值呢？
仍然假设数据arr[0]采用一个空位，arr[1]开始放这个完全二叉树

首先，我们把当前大顶堆的最大值取走，就是root节点了；
之后，取走root节点的大顶堆，就分裂成了两个大顶堆；我们想获取一个次大点，肯定是两个大顶堆的其中一个root节点；
但我们需要把两个大顶锥缝合到一起，不能让大顶堆继续分裂；
少了一个节点后，大顶堆的高度等都可能受影响；
所采用的办法就是，把尾节点拿出来放到root节点位置，做小于log(n)(二叉树层高次)比较换位，补位到对应位置；
尾节点放入root位置后，不平衡到达了二叉树第一层：root->left child, root->right child比大小，大的放到root节点上，与root节点换位；
换位后，不平衡到达了第二层：这个节点可能也就不满足parent >=(left child, right child)了，也需要比较换位；
再次换位后，不平衡达到了第三层：换位节点也可能不满足parent >=(left child, right child)了，也需要比较换位；
,
如果节点提前满足parent比较大，也就平衡了退出；因为下层原来是平衡的，满足parent>=child，这一层平衡不动下一层时，下一层就不需要动。
否则的话，可能要一直执行到最后一层，完成整个平衡；
完成整个平衡后，因为拿走root节点分裂的两个大顶堆，又再次成了一个大顶堆，最大节点又在root了。
持续执行1-4，就可以不断从root节点，拿走剩余的最大值节点，从而完成了数据的排序；

使用它排序的过程，大体是：

for (i=n; i>1; i--){
   swap(arr[i], arr[1]);
   heapify(arr, 1, i-1);
}

对节点从上往下平衡，大体是：

void heapify(int arr[], int v, in n){
  int left = 2*v;
  int right = 2*v + 1;
  int largest = v;
  if (left <=n && arr[left] > arr[v]){
    largest = left;
  }
  if (right <=n && arr[right] > arr[largest]){
    largest = right;
  }
  if (largest != v){
     swap(arr[largest], arr[v]);
     heapify(arr, largest, n);
  }
}

大顶堆-初次构建它

从上面的大顶堆使用角度来说，大顶堆构建好之后，使用起来还是很方便的；
每次小于log(n)次比较，就可以拿到一个剩余节点的最大值，并且维持住其余数据的大顶堆的结构；
效率是比较高的。
那如何构建大顶堆呢？构建难不难呢？
相对构建后的使用来说，还是比较难的，因为它涉及了把所有节点做一次比较放置；

构建的过程，可以参考大顶堆的使用过程，思路主要是：

从底层向下层构建平衡；
例如：对应完全二叉树层高为h，最低层h是叶子节点，不涉及平衡；
从h-1层来检查是否符合大顶堆的平衡，不平衡的父与子中较大的换位达成平衡；
接着从h-2层来检查平衡，不平衡的换位，然后再把h-2层，对该换位节点检查一遍；
接着h-3来检查平衡，不平衡的换位；由于下层已经平衡，有变动了需要，把换位元素向下检查到平衡为止；
接着h-4来检查平衡，不平衡的换位；由于下层已经平衡，有变动了需要，把换位元素向下检查到平衡为止；
具体实现的话，就是从总结点数量 n/2 向前检查，一直检查到头节点1；
检查平衡，如有换位，换位后需要对换位节点向下检查到平衡为止；
这个过程，涉及n/2次从后向前检查，每次检查所使用算法，喝使用大顶堆逐个获取最大元素时，基本一致；
都是查先查该节点平衡，如有换位，则换位元素向下检查到平衡为止；

构建初始大顶堆，的过程大体是：

for (i = n/2; i>=1; i--){
   heapify(arr, i, n);
}

综述

和许多算法的思想类似，都是有规律、有依赖的；

大顶堆的构建过程是自下而上；
大顶堆构建后，节点值替换、再平衡是自上而下的；
先构建下层平衡，下层平衡的基础上，当对节点(包含头节点)做变更时，涉及的重新平衡时，只需要下层每层最多一次换位即可解决；
下层平衡建立后，下层就是一个平衡的大顶堆，节点变更时，下层的下层也是一个平衡的大顶堆；
如果一直需要调整，则沿着需要变更的节点，自顶向下，沿着一条路径下来，形成一个到达叶子节点的通路。

附录

测试程序与测试输出：
—测试输出，仅供参考

arr(20,3,8,4,6,9,10)
arr(3,4,6,8,9,10,20)

—测试程序，仅供参考

#include "stdio.h"
void showarr(int arr[], int n){
  printf("arr(");
  for (int i=1; i<n; i++)
    printf("%d,", arr[i]);
  printf("\b)\n");
}
#define swap(a, b) { a=a+b; b=a-b; a=a-b;}
void heapify(int arr[], int v, int n){
  int left = 2*v;
  int right = 2*v + 1;
  int largest = v;
  if (left <=n && arr[left] > arr[largest])
    largest = left;
  if (right <=n && arr[right] > arr[largest])
    largest = right;
  if (largest != v){
     swap(arr[largest], arr[v]);
     heapify(arr, largest, n);
  }
}
void heapsort(int arr[], int n){
  for (int i=n/2; i>=1; i--)
    heapify(arr, i, n);
  for (int i=n; i>1; i--){
    swap(arr[1], arr[i]);
    heapify(arr, 1, i-1);
  }
}
int main(){
  int arr[] = {0, 20, 3, 8, 4, 6, 9, 10};
  int arrlen = sizeof(arr)/sizeof(int);
  int num = arrlen - 1;
  showarr(arr, arrlen);
  heapsort(arr, num);
  showarr(arr, arrlen);
  return 0;
}

(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)