数据结构-堆结构

堆

• 神奇的堆
• 不多BB直接上代码

#include<iostream>
using namespace std;
//大顶堆
struct Heap{
    int* data;//堆结构 一般不存data[0] ；从data[1]开始存
    int m;//最大可以放得元素个数
    int n;//已经放的元素个数
};
bool isFull(struct Heap*H){
    if(H->n==H->m) return true ;
    else return false;
}
bool isEmpty(struct Heap*H){
    if(H->n==0)return true;
    else return false;
}
struct Heap* creatHeap(int m){
    struct Heap *H=new struct Heap;
    H->data=new int[m+1];//堆的存放是从下标为1的位置开始的
    H->data[0]=9999999;//用作哨兵
    H->n=0;
    H->m=m;
    return H;
};
void insert(struct Heap*H,int data){
    if(isFull(H)){
        cout<<"Full"<<endl;
        return ;
    }
    //n表示当前我准备要放进去的位置
    int n=++H->n;//指向要插入的空着的节点 并且让我们的n加上1；
    for(; /* n>1 && */H->data[n/2]<data;n=n/2) H->data[n]=H->data[n/2];
    //当当前父节点比我的data大 好  ！停住 我就要放在这
    H->data[n]=data;
}
int dele(struct Heap*H){
    if(isEmpty(H)){
        cout<<"empty"<<endl;
        return false;
    }
    int data=H->data[1];
    int temp=H->data[H->n--];
    //parent就是指示我要换的位置
    int parent,child;
    ///如果儿子的下标必须要比已经放入的元素小或等
    for(parent=1;parent*2<=H->n;parent=child){
        child=parent*2;
        if(child!=H->n&&H->data[child+1]>H->data[child])child++;
        //child已经指向最大的孩子元素；
        if(temp>=H->data[child])break;
        else H->data[parent]=H->data[child];
    }
    H->data[parent]=temp;
    return data;
}
//这是一个堆，n下标开始调整
void adjust(struct Heap*H,int n){
    //先把这个元素拿着
    int data=H->data[n];
    int parent,child;
    ///我的孩子的下标必须 要比 总共的元素的下标 小
    for(parent=n;parent*2<=H->n;parent=child){
        child=parent*2;
        if(child!=H->n&&H->data[child+1]>H->data[child])child++;
        if(H->data[child] <= data)break;
        else H->data[parent]=H->data[child];
    }
    H->data[parent]=data;
}
void all_insert(struct Heap*H,int *data,int n){
     for(int a=0;a<n;a++){
        H->data[a+1]=data[a];
        H->n++;
     }
     for(int a=n/2;a>=1;a--){
        adjust(H,a);
     }
}
void show(struct Heap*H){
    for(int a=1;a<=H->n;a++){
        cout<<H->data[a]<<' ';
    }
    cout<<endl;
}
main(){
    int n;
    cin>>n;
    int data[n];
    for(int a=0;a<n;a++){
        cin>>data[a];
    }
    struct Heap*h1=creatHeap(n);
    struct Heap*h2=creatHeap(n);
    for(int a=0;a<n;a++){
        insert(h1,data[a]);
    }
    all_insert(h2,data,n);
    show(h1);
    dele(h1);
    dele(h1);
    show(h1);
    show(h2);
    dele(h2);
    dele(h2);
    show(h2);
}
/*
10
9 8 5 6 3 2 1 4 7  10

10 9 5 7 8 2 1 4 6 3
8 7 5 6 3 2 1 4

10 9 5 7 8 2 1 4 6 3
8 7 5 6 3 2 1 4
 完全一样！！
*/

总结：

• 首先最关键的就是删除操作
• 拿着一个元素待插入到某个位置中
• 从某一个位置开始查找for（我的孩子的下标要比最大的下标小或等）{
  • 找我的孩子中最大的那个
  • 如果拿着的那个元素比孩子最大的那个大于或等于那就break吧（就插这）
  • 要不然就把我孩子移上来
    }
• 结束的时候有两分钟情况 1我没孩子了 就插这把 2我break出来了

堆结构很关键，优先队列，权限，排序中都会用到