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

//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;
}