前面谈到了几种基础排序和快排，分别都用比较简单的方式给大家展示出来了。今天木了半天，眼看今天又要过去了，想了一下 肯定不怎么想学东西了 索性就抽出这点时间来跟整理一下堆排序吧。
一、 从完全二叉树引入堆排序
很多人在看这个的时候肯定就很多人在思考了，到底什么是完全二叉树呢？
来我们先看一下对于完全二叉树的定义：
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
- 所有的叶结点都出现在第k层或k-l层（层次最大的两层）
- 对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树称为完全二叉树。
我们来简单的看一下吧：
额，硬要我说出什么是完全二叉树，我还是说不出来的，就是按照顺序整整齐齐的排列。
二、 来从最简单的二叉树开始说起
现在我们就从开始排序思想了，首先给定一个数组：[5,4 9,1 7,6,2]，然后将该数组装入一个完全二叉树中：
如上图所示，红色的数字代表该项在项目的中的序号。
首先我们将目光关注在根结点处，此时我们发现，他的左孩子和右孩子分别是：2*i+1 2*i+2。此时就出现了二叉树转换的思想：比较父节点和子节点的大小，将最大的节点放在父节点处，就这样一层一层进行递归。其代码如下：
function swap(tree,a,b){
let temp = tree[a];
tree[a] = tree[b];
tree[b] = temp;
}
function heapify(tree,n,i){
if(i>=n) return;
let leftChildNode = 2*i+1;
let rightChildNode = 2*i+2;
let max = i;
if(leftChildNode<n && tree[leftChildNode]>tree[max]){
max = leftChildNode;
}
if(rightChildNode < n&& tree[rightChildNode]>tree[max]){
max = rightChildNode;
}
if(max!==i){
swap(tree,i,max)
heapify(tree,n,max);
}
}
三、 遍历所有的二叉树。
有了上面的代码之后，我们就可以来讲讲堆排序的核心思想了。首先我们用一组来解释过程
image.png
首先将指针拨向
(n-1)/2（2）处，然后通过上面的heapify来比较他和左右子节点的大小。
然后将指针拨向1处，然后通过上面的heapify比较大小。就这样1，4值做一下交换。
同理，就这样不断的偏移指针直到偏移到根结点。这样就找到了整棵树的最大值，即为根结点。
将根结点的值和树最后一个子节点的值做交换。
如图所示，将树的最后一个子节点给移出，此时剩下的值就组成了一个新的树。
以上就是堆排序最核心的思想了，其代码块为：
function findRootNode(tree,n){
let finalParentPoint = Math.floor((n-1-1)/2); // 数组从0开始 所以是从n-1-1开始，这里值得注意一下
for(let i = finalParentPoint;i>=0;i--){
heapify(tree,n,i);
}
}
四、 完成排序。
通过前面的代码 我们就可以很容易的发现：前n项的最大值已经择出来了，而n-1项重新生成了一个无序的树，此时需要的只要考虑到的就只有前n-1项，就这样以此类推，终究得到一个排序好的数组。
具体的代码如下：
function heapSort(tree,n){
findRootNode(tree,n);
console.log(tree)
for(let i=n-1;i>=0;i--){
swap(tree,i,0);
heapify(tree,i,0);
}
}
其完整代码如下：
function swap(tree,a,b){
let temp = tree[a];
tree[a] = tree[b];
tree[b] = temp;
}
function heapify(tree,n,i){
if(i>=n) return;
let leftChildNode = 2*i+1;
let rightChildNode = 2*i+2;
let max = i;
if(leftChildNode<n && tree[leftChildNode]>tree[max]){
max = leftChildNode;
}
if(rightChildNode < n&& tree[rightChildNode]>tree[max]){
max = rightChildNode;
}
if(max!==i){
swap(tree,i,max)
heapify(tree,n,max);
}
}
function findRootNode(tree,n){
let finalParentPoint = Math.floor((n-1-1)/2); // 数组从0开始 所以是从n-1-1开始，这里值得注意一下
for(let i = finalParentPoint;i>=0;i--){
heapify(tree,n,i);
}
}
function heapSort(tree,n){
findRootNode(tree,n);
console.log(tree)
for(let i=n-1;i>=0;i--){
swap(tree,i,0);
heapify(tree,i,0);
}
}
说在最后
关于排序这一块的代码展示，我想这就是我最后一章了。我在接下来的时间里面会重点来写一写，我在项目中遇到的问题（主要是安卓和前端两块）。而算法呢？一般都是我学不进去才花时间来写的，但是不写不知道 真的要把这个东西写清楚是比较麻烦的。特别是堆排序和无向图的最短距离这两章，不仅我写代码想了很久，如何表述清楚也一块也是花费了不少时间的。
本来我计划是今天还写一篇生活类的文章的，但是写完这篇文章都已经11点多了。额，写作不易，如果觉得对您有帮助，可以关注一下。我会定时分享优质内容的。
网友评论