# 堆排序 (最大小堆)

堆排序：堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一颗近似完全二叉树，并且满足子节点的值总是小于 (大于) 他的父节点

** 完全二叉树：** 最下层子节点集中在从左边开始；如果最下层左节点为空，右节点不为空，那么久不是完全二叉树

如图，可以将这颗二叉树分为三个小堆，每一个小堆堆父节点与两个子节点进行比较，选择最大的一个替换父节点

如 A，B，C 三个节点替换之后为 A (10),B (5),C (3)

由此可以写出替换算法

void HeapSort(int tree[],int end,int start){
    int dad=start;
    int son=2*start+1;
    while (son<end){
        if(son+1<end&&tree[son]<tree[son+1]){       //如果左节点小于右节点，那就让子节点位置更新到右节点
            son++;
        }
        if(tree[son]>tree[dad]){
            swap(tree[son],tree[dad]);
            dad=son;
            son=2*dad+1;
        } else{
            return;
        }
    }
}

子节点每次的位置都为父节点✖️2+1，即可对每一个小堆进行遍历替换得到以下结果：

然后从堆堆最底部进行开始替换；

void HeapSwap(int arr[], int len) {
    //i为最后一个节点
    for (int i = len / 2 - 1; i >= 0; i--)
        HeapSort(arr, len, i);
}

由完全二叉树性质可以得到，最后一个父节点为 (len (二叉树长度)/2)-1, 所以，从当前位置开始进行递减替换得到以下结果：

然后最后得到的二叉树堆就是每一个小堆都是父节点最大的结果，根节点为最大值，所以只需每次将最后一个子节点和父节点进行替换并移除添加到数组 (往前一步) 即可最终结果

void Heap(int arr[],int len){
    heap_swap(arr,len);
    for (int i = len - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        HeapSort(arr, i, 0);
    }
}	

完整代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

void HeapSort(int tree[],int end,int start){
    int dad=start;
    int son=2*start+1;
    while (son<end){
        if(son+1<end&&tree[son]<tree[son+1]){       //如果左节点小于右节点，那就让子节点位置更新到右节点
            son++;
        }
        if(tree[son]>tree[dad]){
            swap(tree[son],tree[dad]);
            dad=son;
            son=2*dad+1;
        } else{
            return;
        }
    }
}
void heap_swap(int arr[], int len) {
    //i为最后一个节点
    for (int i = len / 2 - 1; i >= 0; i--)
        HeapSort(arr, len, i);
}
void Heap(int arr[],int len){
    heap_swap(arr,len);
    for (int i = len - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        HeapSort(arr, i, 0);
    }
}
int main(){
    int ans[] = { 5,10,3,6,8,5,2};
    int len=sizeof(ans)/sizeof(int);
    heap_swap(ans,len);
    for(int i=0;i<7;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}