P3378 【模板】二叉堆

这篇具有很好参考价值的文章主要介绍了P3378 【模板】二叉堆。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

[洛谷]P3378 【模板】堆

方法一 手写堆

  • 最小堆插入
    从新增的最后一个结点的父结点开始,用要插入元素向下过滤上层结点(相当于要插入的元素向上渗透)
void siftdown(int i) //传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点开始向下调整 
{
    int t,flag=0;//flag用来标记是否需要继续向下调整
    //当i结点有儿子的时候(其实是至少有左儿子的情况下)并且有需要继续调整的时候循环窒执行
    while( i*2<=n && flag==0 )
    {       
        //首先判断他和他左儿子的关系,并用t记录值较小的结点编号
        if( h[ i] > h[ i*2] )
            t=i*2;
        else
            t=i;
        //如果他有右儿子的情况下,再对右儿子进行讨论
        if(i*2+1 <= n)
        {
            //如果右儿子的值更小,更新较小的结点编号 
            if(h[ t] > h[ i*2+1])
                t=i*2+1;
        }
        //如果发现最小的结点编号不是自己,说明子结点中有比父结点更小的 
        if(t!=i)
        {
            swap(t,i);//交换它们,注意swap函数需要自己来写
            i=t;//更新i为刚才与它交换的儿子结点的编号,便于接下来继续向下调整
        }
        else
            flag=1;//则否说明当前的父结点已经比两个子结点都要小了,不需要在进行调整了
    }
}
  • 最小堆删除
void siftdown(int i) //传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点开始向下调整 
{
    int t,flag=0;//flag用来标记是否需要继续向下调整
    //当i结点有儿子的时候(其实是至少有左儿子的情况下)并且有需要继续调整的时候循环窒执行
    while( i*2<=n && flag==0 )
    {       
        //首先判断他和他左儿子的关系,并用t记录值较小的结点编号
        if( h[ i] > h[ i*2] )
            t=i*2;
        else
            t=i;
        //如果他有右儿子的情况下,再对右儿子进行讨论
        if(i*2+1 <= n)
        {
            //如果右儿子的值更小,更新较小的结点编号 
            if(h[ t] > h[ i*2+1])
                t=i*2+1;
        }
        //如果发现最小的结点编号不是自己,说明子结点中有比父结点更小的 
        if(t!=i)
        {
            swap(t,i);//交换它们,注意swap函数需要自己来写
            i=t;//更新i为刚才与它交换的儿子结点的编号,便于接下来继续向下调整
        }
        else
            flag=1;//则否说明当前的父结点已经比两个子结点都要小了,不需要在进行调整了
    }
}
//删除最小数
void del(){
	dui[1]=dui[d];
	d--;
	shitdown(1);
}

方法二 STL

c++优先队列(priority_queue)用法详解文章来源地址https://www.toymoban.com/news/detail-532859.html

#include<bits/stdc++.h>
using namespace std;
int n,d;
int main(){
	priority_queue<int,vector<int>,greater<int> > dui;
	cin>>n;
	for(int i=1;i<=n;i++){
		int op;
		cin>>op;
		if(op==1){
			int num;
			cin>>num;
			dui.push(num);			
		}
		else if(op==2)
			cout<<dui.top()<<endl;
		else if(op==3)
			dui.pop();
	}
	return 0;
}

到了这里,关于P3378 【模板】二叉堆的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 一套模板搞定二叉树算法题--二叉树算法讲解003

    题目和题意: 图示: 题解: 题目和题意: 题解: 题目和题意: 题解: 题目和题意: 题解1: 写法1: 写法2: 题解2: 题目和题意: 题解:该题与叶子节点强相关,和自顶向下或自底向上并不强相关。 自底向上的图示: 题目和题意: 题解: 简洁写法: 思路易理解,代码

    2024年02月19日
    浏览(35)
  • 【cobra】手写你的第一个命令行脚手架工具 | cobra整合go template通过终端以命令行方式生成.drone.yml 模板

    本次教程使用的开源框架如下: 名字 开源地址 作用 Cobra 命令行工具 https://github.com/spf13/cobra Aurora 字体颜色 https://github.com/logrusorgru/aurora go-zero go-z框架 模板功能 https://github.com/zeromicro/go-zero 本项目完整源码 :https://github.com/ctra-wang/cobra-gen-drone 概述 :Cobra 是一个 Golang 包,它

    2024年02月16日
    浏览(45)
  • 数据结构与算法—二叉树数组表示(ArrayBinTree)、二叉树的链式表示(LinkedBinTree)的基于C++模板代码实现

    1、二叉树的顺序表示:ArrayBinTree.h 二叉树的顺序表示法操作方便,但缺点是容易造成存储空间浪费。 这是一个用数组实现的二叉树类模板。它可以创建一个空树,也可以在指定的位置插入结点并设置结点的值,可以删除子树,并支持逐层遍历。使用该类时,需要提供一个元

    2024年02月06日
    浏览(44)
  • 这些方法可以手写扫描识别

    小伙伴们知道有一项技术是可以将我们手写的东西识别出来吗?这一项创新的技术就是手写识别功能,它能够将手写内容快速转换为数字或文本格式,并提高信息处理和管理的效率。而且相比传统的手工记录方式,手写识别功能具有较高的准确性、更为广泛的应用场景以及更

    2024年02月08日
    浏览(39)
  • JavaScript 手写代码 第七期(重写数组方法三) 用于遍历的方法

    我们在日常开发过程中,往往都是取出来直接用,从来不思考代码的底层实现逻辑,但当我开始研究一些底层的东西的时候,才开始理解了JavaScript每个方法和函数的底层实现思路,我认为这可以很好的提高我们的代码水平和逻辑思维。 2.1.1 基本使用 forEach() 方法用于调用数组

    2024年02月12日
    浏览(52)
  • 洛谷——SP1-TEST - Life, the Universe, and Everything +注册SPOJ的方法

    从输入读取数字并输出,每行一个,直到读到 42 42 42 停止。 Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely… rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two d

    2024年02月07日
    浏览(35)
  • JavaScript 手写代码 第六期(重写数组方法二)不改变原数组的方法

    我们在日常开发过程中,往往都是取出来直接用,从来不思考代码的底层实现逻辑,但当我开始研究一些底层的东西的时候,才开始理解了JavaScript每个方法和函数的底层实现思路,我认为这可以很好的提高我们的代码水平和逻辑思维。 2.1.1 基本使用 join() 方法用于把数组中的

    2024年02月11日
    浏览(51)
  • JavaScript 手写代码 第五期(重写数组方法一)-可以改变原数组的方法

    我们在日常开发过程中,往往都是取出来直接用,从来不思考代码的底层实现逻辑,但当我开始研究一些底层的东西的时候,才开始理解了JavaScript每个方法和函数的底层实现思路,我认为这可以很好的提高我们的代码水平和逻辑思维。 push 从后面添加元素 返回push完以后数组

    2024年02月11日
    浏览(46)
  • js--手写call和apply方法干货注释满满

    我们都知道js中call和apply都是改变this指向的,这篇文章我们一起来实现call和apply的底层吧!我们先来看一下js中的call和apply的用法 一.用法 1.call用法 传递参数逗号分隔 2.apply用法 传递参数为数组 二.手写实现call 1.手写myCall改变this指向 这里this指向已经改变,但是还不可以传递

    2024年02月06日
    浏览(43)
  • JS中数组的splice()方法介绍 及 用原生JS手写数组splice()方法

    先介绍splice 一、splice()方法是用来对数组进行增、删操作,该方法返回被删除的元素,改变原数组 二、splice()方法接受三个及以上的参数:        第一个参数: 第一个参数是起始位置(数组的索引)       第二个参数: 第二个参数是要删除的元素个数,如果该参数是负数则默

    2024年02月07日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包