当我们需要高效的完成以下操作时: 1.插入一个元素 2.取得最小(最大)的数值,并且删除 能够完成这种操作的数据结构叫做优先队列 而能够使用二叉树,完成这种操作的数据结构叫做堆(二叉堆) 堆与优先队列的时间复杂度: 若共有n个元素,则可在O(logn)的时间内完成上述两种操作 堆的结构如下图: 堆最重要的性质就是儿子的值一定不小于父亲的值,且堆从上到下,从左到右紧密排列. 堆的操作: 当我们希望向堆中插入元素时,堆的内部会进行如下操作(以插入元素3为例): (1.在堆的末尾插入该值) (2.不断

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far. Input The first line of input contains a single int

题目链接:http://poj.org/problem?id=2442 Time Limit: 6000MS Memory Limit: 65536K Description Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's clear that we ma

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2151 这道题因为优先队列不怎么会用,而且手写堆的代码也不长,也想复习一下手写堆的写法……结果……WAWAWAWAW……看来我对堆的认识还是太浅薄了…… 这道题,如果没有限制不能选相邻的两个位置,那就肯定是贪心地选择m个美观度最大的位置种树.然而这里加了限制,那么我们可以注意到,如果一个美观度比较大的位置不被选上,一定是因为它两边的位置都被选了. 于是我们可以把n个美观度压进一个堆里,每

堆其实也是树结构(或者说基于树结构),一般可以用堆实现优先队列. 二叉堆 堆可以用于实现其他高层数据结构,比如优先队列 而要实现一个堆,可以借助二叉树,其实现称为: 二叉堆 (使用二叉树表示的堆). 但是二叉堆,需要满足一些特殊性质: 其一.二叉堆一定是一棵完全二叉树 (完全二叉树可以用数组表示,见下面) 完全二叉树缺失的部分一定是在右下方.(每层一定是从左到右的顺序优先存放) 完全二叉树的结构,可以简单理解成按层安放元素的.(所以数组是不错的底层实现) 其二.父节点一定比子节点大 (针对大顶堆

题目描述 5710. 积压订单中的订单总数 题解 题目不难,主要是要读懂题意,一步步模拟,代码较长,需要细心检查. 坑较多,比如我犯了很多傻逼问题:想都不想就拿1<<9+7当作1000000007,更傻逼的是,<<的优先级低于+号,<<都没用对. 实时取最大和最小,可以用堆或者优先队列实现.这里我使用了Java的TreeMap. class Solution { public static int getNumberOfBacklogOrders(int[][] ord

题目:http://poj.org/problem?id=1442 题意:n,m,分别是a数组,u数组的个数,u[i]w为几,就加到a几,然后输出第i 小的 刚开始用了一个小顶堆,超时,后来看了看别人的 代码,很巧妙的设计 #include<stdio.h> #include<queue> using namespace std; ]; int main() { int n,i,m,j,u; priority_queue< int,vector<int>,less

前言 话说新开的博客十分好用... 所以,我打算开一个坑,名曰[算法系列]. 什么意思--从名字泥应该就猜得出来... 废话不多说,进入正文~~ 正文 原理 首先,堆是一颗棵二叉树.. 其次,堆是一棵完全二叉树.. 然后,设有一关系 P(Type X, Type Y) 则,堆的每个元素 Element 满足: foreach Child ∈ Element.Childs do ASSERT( P(Element.value, Child.value) ); 说的明白点,就是每个元素和它的儿子有特

传送门 首先,把A和B两个序列分别从小到大排序,变成两个有序队列.这样,从A和B中各任取一个数相加得到N2个和,可以把这些和看成形成了n个有序表/队列: A[1]+B[1] <= A[1]+B[2] <= … <= A[1]+B[N] A[2]+B[1] <= A[2]+B[2] <= … <= A[2]+B[N] …… A[N]+B[1] <= A[N]+B[2] <= … <= A[N]+B[N] 接下来,就相当于要将这N个有序队列进行合并排序:

题目描述 给出一个长度为NNN的非负整数序列AiA_iAi​,对于所有1≤k≤(N+1)/21 ≤ k ≤ (N + 1) / 21≤k≤(N+1)/2,输出A1,A3,…,A2k−1A_1, A_3, …, A_{2k - 1}A1​,A3​,…,A2k−1​的中位数.即前1,3,5,…1,3,5,…1,3,5,…个数的中位数. 输入输出格式 输入格式: 第1行为一个正整数N,表示了序列长度. 第2行包含N个非负整数Ai​(Ai​≤109). 输出格式: 共2(N+1)/2行,第iii行为A1

剑指 Offer 41. 数据流中的中位数 Offer_41 题目详情 题解分析 本题使用大根堆和小根堆来解决这个寻找中位数和插入中位数的问题. 其实本题最直接的方法是先对数组进行排序,然后取中位数.但是,这种方法的此方法的时间复杂度为 O(N),其中包括: 查找元素插入位置 O(logN) (二分查找).向数组某位置插入元素 O(N)(插入位置之后的元素都需要向后移动一位). 建立一个 小顶堆 A 和 大顶堆 B ,各保存列表的一半元素,且规定: 3.1 A 保存 较大 的一半,长度为 \(\

题目描述 给定m个序列,每个序列包含n个非负整数.现在我们可以从每个序列中选择一个数字以形成一个具有m个整数的序列.显然,我们可以得到n ^ m种这种序列.然后,我们可以计算每个序列中的数字总和,并获得n ^ m个值.我们需要的是最小的n个和.你可以帮我们吗? 题目大意:给定M个长度为N的序列,从每个序列中任意取一个数求和,可以构成N的M次方个和,求其中最小的N个和. 输入格式 第一行是整数T,它显示测试用例的数量,然后是T个测试用例.每种情况的第一行都包含两个整数m,n(0 <m <= 10

二叉堆 1 二叉堆的定义 堆是一个完全二叉树结构(除了最底下一层,其他层全是完全平衡的),如果每个结点都大于它的两个孩子,那么这个堆是有序的. 二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级存储(不用数组的第一个位置) 2 二叉堆的性质 最大的元素在a[1] (root结点) 每个k的父亲在k/2 每个k的孩子在k*2和k*2+1 3 二叉堆的操作 3.1 上浮(孩子大于父亲)——对应插入操作 循环,每次比较自己和父亲,如果比父亲大就交换,直到root. 3.2 插入 先把元

1.最小堆.最大堆 priority_queue<int,vector<int>,greater<int> > f; //最小堆(后面的数逐渐greater) priority_queue<int,vector<int>,less<int> > f;//最大堆(后面的数逐渐less) (1).合并果子 https://www.vijos.org/p/1097 #include <cstdio> #include <c

题目链接:http://poj.org/problem?id=2431 题意:一辆卡车需要行驶 L 距离,车上油的含量为 P,在行驶的过程中有 n 个加油站 每个加油站到终点的距离是ai,每个加油站最多给卡车加 b 单位的油:求最后到达终点需要加油的最少次数:如果不能到达,输出-1: 我们可以从起点开始算,看每次油箱中的油是否能够到达下一个加油站,如果不能就加上已经经过的加油站的所能加的最大加油量,如果能到达,就记录一下此加油站可以被加进去:因为我们每次都需要加进去最大的加油 量,所以我们可以用

[0]README 0.1)为什么有这篇文章?因为 Dijkstra算法的优先队列实现 涉及到了一种新的数据结构,即优先队列(二叉堆)的操作需要更改以适应这种新的数据结构,我们暂且吧它定义为Distance, 而不是单纯的int类型: 0.2)本文源代码均为原创, int类型的优先队列(二叉堆)的操作实现,参见http://blog.csdn.net/PacosonSWJTU/article/details/49498255, (并比较他们的打印结果,很有必要) [1]因为 Dijkstra算法

2.4.4 堆的算法 我们用长度为 N + 1的私有数组pq[]来表示一个大小为N的堆,我们不会使用pq[0],堆元素放在pq[1]至pq[N]中.在排序算法中,我们只能通过私有辅助函数less()和exch()来访问元素,但因为所有的元素都在数组pq[]中,我们在2.4.4.2节中会使用更加紧凑的实现方式,不再将数组作为参数传递.堆的操作会首先进行一些简单的改动,打破堆的状态,然后再遍历堆并按照要求将堆的状态回复.我们称这个过程叫做堆的有序化(reheapitying). 堆实现的比较和交换方

6326.Problem H. Monster Hunter 题意就是打怪兽,给定一棵 n 个点的树,除 1 外每个点有一只怪兽,打败它需要先消耗 ai点 HP,再恢复 bi点 HP.求从 1 号点出发按照最优策略打败所有怪兽一开始所需的最少 HP. 直接贴官方题解吧,这个题写的脑壳疼. 官方题解: 其实就是一直合并节点,最后合并到只有一个节点就是结果,具体的不想说什么了,这个题看了好久了,不想再看到他了... 代码是个人理解+个人习惯+综合多个题解写的.mdzz,我要撞墙... 代码: //1

题目链接:http://poj.org/problem?id=2051 ///维持最小堆(优先队列)POJ2051 #include <iostream> #include <string> using namespace std; struct Node { int Now; ///出堆的时间 int id; int p; ///时间间隔 }; Node node []; int K; ///输出个数 void down (Node H[],int s,int m) { ///向

Luogu P4779 利用堆/优先队列快速取得权值最小的点. 在稠密图中的表现比SPFA要优秀. #include<iostream> #include<cstdio> #include<queue> using namespace std; struct data { long long next,to,val; }edge[500005]; long long cnt,head[500005],n,m,s,u,v,w,cost[500005]; bool vis[

题意: 按照顺序给你n个数,当数的数量是奇数的时候就输出它们的中位数 题解: 优先队列默认是大顶堆,即priority_queue.top()是这个队列中的最大值 那么我们就可以先创造一个大顶堆优先队列qmax,和一个小顶堆qmin qmin里面放的是大于等于中位数的数,qmax里面放的是比中位数小的数 因为qmin是小顶堆,那么qmin.top()肯定就是中位数 (上面的话是在中位数的前提下) 代码: 1 #include <bits/stdc++.h> 2 using namespace