随笔，【数据结构-二叉树】堆（Heap）

堆是属于数据结构树的一个分支，它其实就是一颗二叉树，堆分有大顶堆和小顶堆

大顶堆：父节点的值永远大于子结点

小顶堆：父节点的值永远小于子结点

在堆中插入元素，我们一般在尾部插入，然后又个上浮操作（以大根堆为操作）

来个动态图

视频警告：播放链接不能为空

那取出头节点就不说了，主要来说说删除头节点

得有个下浮的过程，我们一般会把头节点复制一份放在堆的后面一位（堆排序有用），然后对左右子结点进行操作，然后再进行操作，一直把头节点移到最后，然后堆的长度减一

堆排序就是每次对堆进行pop操作，然后这时候相当于每次都是把最大（最小）值给放到了最后（堆顶一定最大）

下面是源代码：

//https://blog.csdn.net/gsjwxhn/article/details/103051851
#include <bits/stdc++.h>
using namespace std;
template<typename T>
class Tree{
    private:
        T *data=NULL;
        int count=0;//当前树的长度
        int length=0;//表示堆的最大容量
    public:
        Tree(int length){
            data = new T[length+1];
            this->length = length+1;
        }
        void print(){
            for (int i = 1; i < length; ++i) {
                cout<<this->data[i]<<" ";
            }
        }
        void set_Data(T *data){
            this->data = data;
        }
        void Insert(T data){
            this->data[++count]=data;
            percolate_up(count);//上浮
        }
        void percolate_up(int cnt){
            while(cnt>1 && data[cnt]>data[cnt/2]){
                swap(data[cnt],data[cnt/2]);
                cnt/=2;
            }
        }
        T pop_Head(){
            T data =this->data[1];
            swap(this->data[1],this->data[count--]);
            percolate_Down(1);//下浮
            return data;
        }
        void percolate_Down(int cnt){
            //count是当前结点个数4
            //cnt=2
            while(cnt*2<=count){
                int j=cnt*2;
                if(j+1<=count&&data[j]<data[j+1])j++;
                if(data[cnt]>data[j])break;
                swap(data[cnt],data[j]);
                cnt=j;
            }
           count--;
        }
};
int main(){
    Tree<int> Heap =Tree<int>(10);
//    9 2 5 1 7 8 3 6 4 10
    for (int i = 0; i < 10; ++i) {
        int k;
        cin>>k;
        Heap.Insert(k);
    }
    Heap.print();
    cout<<endl;
//下面是堆排序的操作
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.pop_Head();
    Heap.print();
    return 0;
}