1.堆

1.1 什么是堆

堆就是一个完全二叉树，父节点大于子节点的称之为最大堆，子节点大于父节点的称之为最小堆，至于完全二叉树的概念为：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

1.2 如何表达一个完全二叉树

这里使用数组来表达完全二叉树，由完全二叉树可以看出可以完美的使用数组进行表示，表示方法为，从左到右，从上到下，依次生成一个数组
以一个例子来表示：

从数组表示完全二叉树，可以得到许多结论，这些结论下面用到：
如果需要处理索引节点为i处的数，那么很容易可以得到他的父节点为(i - 1)/2，它的左孩子节点为2*i + 1，它的右孩子节点为2*i + 2。
比如从上图可以看到：节点3的父节点为(3 - 1)/2 = 1，其左孩子节点为2*3+1=7，其右孩子节点为2*3+2=8。

2.生成最大堆

2.1 heapify

这个需要结合生成大顶堆的整体流程来看，本博客采用从下往上生成大顶堆。先看代码，结合代码理解，具体注释已经写入代码中：

void heapify(vector<int>& tree, int i, int n){
    //递归出口
    if(i >= n) return;
    //两个子节点的索引位置
    int c1 = 2*i+1;
    int c2 = 2*i+2;
    //找到最大的节点位置，注意判断不要越界
    int max = i;
    if(c1 < n && tree[max] < tree[c1]) max = c1;
    if(c2 < n && tree[max] < tree[c2]) max = c2;
    //将最大节点放在父节点上
    if(max != i){
        swap(tree[i], tree[max]);
        heapify(tree, max, n);
    }
}

heapify是在该节点处生成最大堆，但是仅仅依靠它是不能实现的，它需要有铺垫和前提，就是它的子树已经是最大堆了。所以仅靠这一个函数是无法实现生成最大堆，还需要从下往上进行遍历给heapify函数做铺垫。

2.1 生成最大堆

根据完全二叉树转化的数组，可以得到，完全二叉树从下往上生成堆，也就是对数组进行从后往前遍历，所以首先找到最后一个节点的父节点，然后进行数组从后往前遍历即可。代码如下：

void build_heap(vector<int>& tree){
    //最后一个节点
    int lastnode = tree.size() - 1;
    //最后一个节点的父节点
    int parent = (lastnode - 1)/2;
    for(int i = parent; i >= 0; i--){
        heapify(tree, i, tree.size());
    }
}

3.堆排序

首先使用build_heap生成最大堆，有最大堆的原理可得：最大堆的根节点为堆的最大值，所以将根节点与最后一个节点交换，删除最后一个节点，使用heapify再次进行最大堆生成，这里并没有删除最后一个节点，只是再进行下一次排序时，没有包含最后一个节点，具体代码如下：

void heapsort(vector<int>& nums){
    //先生成最大堆
    build_heap(nums);
    for(int i = nums.size() - 1; i >= 0; i--){
        swap(nums[0], nums[i]);
        //因为堆已经生成，所以只需要heapify即可
        //最后一个不用参加heapify
        heapify(nums, 0, i);
    }
}

4.整体代码

#include <iostream>
#include <vector>
using namespace std;
//堆排序，完全二叉树，父节点大于子节点，叫做堆
//用代码表示一个堆，用数组表示，从上往下，从左往右
//heapify，heapify，这里需要结合从下从上生成堆的整体概念进行理解
//如果仅仅理解heapify，可以看出，仅靠heapfiy无法堆，
//因为需要从下往上生成堆，因此表明下面没有打乱顺序的子树已经是堆了，所以我们只要对交换顺序后的子节点对应的子树进行递归就能生成堆了。
//这样已知一个节点在数组的索引为i，可以求出父节点为(i-1)/2，左子节点为2*i+1，右子节点为2*i+2
//对一个节点进行heapify,往下递归
void heapify(vector<int>& tree, int i, int n){
    //递归出口
    if(i >= n) return;
    //两个子节点的索引位置
    int c1 = 2*i+1;
    int c2 = 2*i+2;
    //找到最大的节点位置，注意判断不要越界
    int max = i;
    if(c1 < n && tree[max] < tree[c1]) max = c1;
    if(c2 < n && tree[max] < tree[c2]) max = c2;
    //将最大节点放在父节点上
    if(max != i){
        swap(tree[i], tree[max]);
        heapify(tree, max, n);
    }
}
//对所有节点进行heapify，也就是生成堆
//按照树的顺序是，从右往左，从下往上依次heapify，按照数组就是，从后往前进行遍历
void build_heap(vector<int>& tree){
    //最后一个节点
    int lastnode = tree.size() - 1;
    //最后一个节点的父节点
    int parent = (lastnode - 1)/2;
    for(int i = parent; i >= 0; i--){
        heapify(tree, i, tree.size());
    }
}
//用堆排序，最大值肯定在堆的最上面的父节点，
//只要生成堆，然后让最上面的父节点与最后一个节点进行交换即可，然后删除最后一个节点，再生成堆
void heapsort(vector<int>& nums){
    //先生成最大堆
    build_heap(nums);
    for(int i = nums.size() - 1; i >= 0; i--){
        swap(nums[0], nums[i]);
        //因为堆已经生成，所以只需要heapify即可
        //最后一个不用参加heapify
        heapify(nums, 0, i);
    }
}
int main() {
    vector<int> nums = {2, 9, 3, 7, 1, 6, 5, 4, 8};
    heapsort(nums);
    for(int i = 0; i < nums.size(); i++){
        cout<<nums[i]<<" "<<endl;
    }
    return 0;
}