https://www.bilibili.com/video/BV19A411q7mn?t=1007

堆的基本操作及堆排序

//堆的插入删除和堆排序
//堆排序：在每次堆的删除中，取出的根节点就是最小的  自然完成了排序
#include<iostream>
using namespace std;
const int n = 7;
int a[n] = { 3,5,1,7,6,4,2 };//待排序的数组
int heap[200];//堆数组
int len;//堆长度

void insert(int x)//把元素x插入最小堆
{
    int pa, son;//下标，指针
    heap[0] = -10000;//哨兵
    son = ++len;
    pa = son / 2;
    while (x < heap[pa])
    {
        heap[son] = heap[pa];//上面元素下移
        son = pa, pa = son / 2;//下标上浮

    }
    heap[son] = x;//插入x
}
int dele()//取出并删除根元素
{
    int pa, son;
    int h = heap[1];//保存根元素
    int t = heap[len--];//保存尾元素
    pa = 1, son = 2 * pa;
    while (son <= len)
    {
        if (son < len && heap[son + 1] < heap[son])  son++;//如果右孩子小，就指向右孩子
        if (t <= heap[son]) break;
        heap[pa] = heap[son];//下面元素上移
        pa = son, son = 2 * pa;//下标下沉
    }
    heap[pa] = t;//返回尾元素
    return h;//返回根元素

}
int main()
{

    for (int i = 0; i < n; i++)   insert(a[i]);
    for (int i = 1; i <= n; i++) cout << dele() << " ";
    return 0;
}