上面是一个完全二叉树（一般的完全二叉树有点不同），优先排满左边，用这个理解堆排序
堆排序(从小到大为例)
首先，这个用到了树进行描述，但是这个只是为了减少复杂度，其实堆排序实际上没有构建一个树形结构，而是通过了运算模拟了树，所以，只需要知道树长什么样的，就可以理解这篇文章了
如果是想直接看代码，文末有代码，可以看着代码和算法分析，对比着看
概念：
最大堆：（一个完全树），所有的根节点的数的都比子节点的数要大，那么就说这是一个最大堆
要知道，怎么通过数字的计算：（如下构建一个数组）
[0][1][2][3][4][5][6][7][8][9][10]
假设是上面这样的的一个数组
(这个数组很特殊，下标恰好是数据内部内容)
[0] 的子节点是[1] [2]。[1] 的子节点是[3] [4]。[2]的子节点是[5] [6]....以此类推（如果你懂了广度搜索，那么看这个会非常简单；同样，你要是理解了这个，看广搜也会是非常简单了）
我们这里构建一个二叉树:
parent(i) = (i - 1)/2（向下取整，通过这样的方式找到父节点）
left(i) = 2*i +1(这是二叉树的左节点，i是一个父节点)
right(i) = 2*i + 2（这是二叉树的右节点，i是一个父节点）
这样的话，就算是这是一个数组，都可以构建一个二叉树了。在逻辑上构建好了
和一般的讲法不同，我先讲算法思路，因为我觉得这样更好理解
算法思路：找到最大那个数，将这个数放到数组的最后面。(其实跟很多其他的排序方式都是一样的)
为什么要构建这个最大堆，其实理由很简单
对于一个三个数构成树，那么这样的最大堆就实现了最大的那个数就会出现在这个只有三个数构建的数的最顶端(每一个根节点都比子节点大)
这样，我们就更容易拿到那个最大数了。要知道，如果我们是从最深层开始遍历的，那么先把最底层的那些数中的最大数都拿出来了，进入了倒数第二层。那么一直往回走，进入到了倒数第三之后，第二次的数已经是倒数一二层中最大的了，那么再把其中的最大放到了第三层....一直这样，走到根节点，那么根节点中的数，就会是整个堆中最大的那个数了。
同时【关键！！】由于，我们之前的往回走，保证了每一层的父节点都是比子节点的要大的，那么就可以说是，左右两边的树本身就是一个最大堆【这个性质非常重要，先记住这个，那么接下来的算法就是迎刃而解了】
要知道，之前那个部分很好，实现了所有的数中最大的那个到达了最顶端，但是实际上，其他部分，还是没有排序好的。我们现在有的，只是一个最顶端(那个根)的左右树都是最大堆(这个在之前的遍历过程就已经实现了)。
下一步的操作就是将这个最大的点，和整个堆最后的那个数进行调换(记住，这个最后的位置是会变的，如果已经排好的位置，我们就不管了，这样最后的那个数，其实就是在说“最后的那个还没有排好的那个数”)。
【很重要的一点】，在调换之后，不是那个整个树的最顶端就没有不符合了最大堆的定义了么？那么我们就需要实现恢复。这个恢复的复杂度只有O(log n) （n是整个树的规模，记住这个n会递减的，上面一段讲述了）
前提是 左右两边的树都是最大堆
这恢复的代码如下:
int *a, size; // a是一个数组，size是我们设置那个堆的大小，不是数组的大小
void max_Heapify(int i){ // 假设左右堆都是最大堆了
int l = 2*i + 1; // 得到左子树
int r = 2*i + 2, largest = i; // 得到右子树
if (l < size && a[l] > a[largest])
largest = l;
if (r < size && a[r] > a[largest])
largest = r;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp; // 交换父节点和两个最大堆的根节点
max_Heapify(largest);
}
} // 用于维护最大堆
上面的代码，其实建立在左右都是最大堆的前提下的。
当然如果左右只有一个数，那么左右本身就是一个最大堆，那么就这个回复过程，其实是实现了前文所述的三个数所构建的树。
接下来就实现怎么建初始的最大堆呢？
还是利用前文的分析
void build_max_Heapify(){ // 相当于从最后一层开始建堆
for(int i = size / 2 - 1; i >= 0;--i){
max_Heapify(i);
}
}
首先最后一层肯定是不用看的，因为他们没有子节点，也就说他们本身就是最大的那个。
那么就直接从，最后那个数的父节点来看。
有人可能要问了，上面那个为什么是size/2-1呢？
要知道，计算机语言一般都是从0开始计数的。所以，size是整个堆的大小，那么堆的最后一个数的下标其实是size-1，那么根据最开始给出的算的公式parent(i) = (i - 1)/2 (向下取整)。
那么最后那个数其实的父节点其实是，(size - 2) / 2 (向下取整)。
那么就是size / 2(向下取整) - 1。
在C\C++中，也就是size/2 - 1
如果对于上面的没有疑问了，那么就可以往下看了
上面实现了两个操作，一个是建最大堆的过程，一个是回复最大堆的过程，其实，整个堆排序的大体就一个完成了。
剩下的就是，每一次将最大那个数放到堆的最后面之后，就再对前面没有排序好（但是，任然是一个在根部的左右两边的都是最大堆的一个数，因为每次，只是改变最顶端的那个数）的部分再进行恢复
代码如下：
void HeapSort(){
build_max_Heapify(); // 构建最大堆
for (int i = size-1; i > 0; --i) {
int temp = a[i];
a[i] = a[0];
a[0] = temp;
size -= 1;
max_Heapify(0); // 恢复顶端
}
}
整个代码如下：(加上了main函数的)
#include <iostream>
using namespace std;
int *a, size; // a是一个数组，size是我们设置那个堆的大小，不是数组的大小
void max_Heapify(int i){ // 假设左右堆都是最大堆了
int l = 2*i + 1; // 得到左子树
int r = 2*i + 2, largest = i; // 得到右子树
if (l < size && a[l] > a[largest])
largest = l;
if (r < size && a[r] > a[largest])
largest = r;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp; // 交换父节点和两个最大堆的根节点
max_Heapify(largest);
}
} // 用于维护最大堆
void build_max_Heapify(){ // 相当于从最后一层开始建堆
for(int i = size / 2 - 1; i >= 0;--i){
max_Heapify(i);
}
}
void HeapSort(){
build_max_Heapify(); // 构建最大堆
for (int i = size-1; i > 0; --i) {
int temp = a[i];
a[i] = a[0];
a[0] = temp;
size -= 1;
max_Heapify(0);
}
}
int main(){
int n;
cin >> size;
n = size;
a = new int[n]; // 申请空间
for (int i = 0; i < size; ++i) {
cin >> a[i]; // 数据读入
}
HeapSort(); // 排序
for (int i = 0; i < n; ++i) {
cout << a[i]<< " "; // 排序后输出
}
cout << endl;
delete[] a; // 释放空间
}
网友评论