洛谷P3378 二叉堆模板

最新推荐文章于 2024-09-17 09:57:56 发布

animalcoder

最新推荐文章于 2024-09-17 09:57:56 发布

阅读量211

点赞数 1

CC 4.0 BY-SA版权

分类专栏： ACM--堆文章标签：堆

本文链接：https://blog.csdn.net/animalcoder/article/details/100157269

ACM--堆专栏收录该内容

1 篇文章

订阅专栏

本文深入探讨了小根堆这一高效数据结构的性质及其实现。详细介绍了小根堆的三种基本操作：添加元素、查询根顶元素、删除根节点，并通过具体代码示例展示了如何在C++中实现这些操作。适用于对数据结构和算法有需求的学习者和开发者。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

小根堆性质：左儿子=>根节点<=右儿子

三个操作：1.添加x O(logn) 2.查询根顶O(1) 3.删除根节点 O(logn)

添加：末尾先加x,然后不断与更小的上移(交换)

删除：先将点1跟k交换，然后点1不断下移(交换)，跟更小的儿子交换

保持性质不变

//luoguP3378 小根堆模板
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string.h>
using namespace std;
#define ll long long

namespace Heap{

    int h[1000005];int k=0;
    void add(int x){
        h[++k]=x;
        int y=k;
        while(y>1&&h[y/2]>h[y]){
            swap(h[y/2],h[y]);
            y=y/2;
        }
    }
    int get(){
        return h[1];
    }
    void pop(){
        swap(h[1],h[k]);--k;
        int x=1,y=2;
        while((y<=k&&h[y]<h[x])||(y+1<=k&&h[y+1]<h[x])){
            if(y+1<=k&&h[y]>h[y+1])y++;//选y还是y+1
            swap(h[x],h[y]);
            x=y;y*=2;
        }
    }
}


int main(){

    int n;cin>>n;
    while(n--){
        int t;cin>>t;
        if(t==1){
            int x;cin>>x;
            Heap::add(x);
        }
        if(t==2){
            cout<<Heap::get()<<endl;
        }
        if(t==3){
            Heap::pop();
        }
    }


    system("pause");
    return 0;
}