山东省建设厅网站查,dw如何制作自己的网站,做网站大量视频怎么存储,led灯 东莞网站建设堆
堆是完全二叉树#xff0c;即除了最后一列之外#xff0c;上面的每一层都是满的#xff08;左右严格对称且每个节点都满子节点#xff09; 最后一列从左向右排序。
默认大根堆#xff1a;每一个节点都大于其左右儿子#xff0c;根节点就是整个数据结构的最大值 pr…堆
堆是完全二叉树即除了最后一列之外上面的每一层都是满的左右严格对称且每个节点都满子节点 最后一列从左向右排序。
默认大根堆每一个节点都大于其左右儿子根节点就是整个数据结构的最大值 priority_queueint, vectorint, lessint q;或者priority_queueint q; 小根堆每一个节点都小于其左右儿子根节点就是整个数据结构的最小值 priority_queueint, vectorint, greaterint q; 题目838. 堆排序 - AcWing题库
题解
本题使用使用小根堆。 heap[]表示模拟整个树的数组size表示整个数组的长度 up(x),down(x)来维护整个二叉树。up将小的值上浮down将大的值下沉都是递归的思想 1.插入一个数heap[ size] x ;up(size)。先将其插入到最后一列然后向上上浮
2.求集合当中的最小值 heap[1]
3.删除最小值 heap[1]heap[size];size--;down(1) 4.删除任意一个元素 heap[k]heap[size];size--;up(k);down(k)。不是上升就是下沉堆只会执行一个操作。当执行up(操作时说明k代表的数值较小所以会上浮那么就一定不会down()下沉; 5.修改任意一个元素heap[k]x;down[k];up[k]; 4、5。stl优先队列不可直接实现 用一维数组来存下标从1开始。左右节点2x2x1。若从0开始那一开始的左节点等于根节点了 代码
本体的暴力解法可以直接sort( )在这里不再给出。
#includebits/stdc.husing namespace std;const int N1e510;
int heap[N],ans;void down(int x)
{int ux;if(x*2ans heap[u]heap[2*x]) u2*x;if(2*x1ans heap[u]heap[2*x1]) u2*x1;//如果不相等就代表根节点不是最小的此时根节点数组对应的下标已经被子节点的下标覆盖if(u!x){//交换值使根节点变成最小的swap(heap[x],heap[u]);down(u);}
}
int main()
{int n,m;cin n m;for(int i1;in;i) cin heap[i];ansn;//构建二叉树for(int in/2;i;i--) down(i);while(m--){cout heap[1] ;
//输出完后依照本题根节点就没用了需要删掉然后输出下一次的根节点
//让根节点等于本二叉树中最大的值heap[1]heap[ans];
//整个二叉树的长度减一ans--;
//让根节点下沉down(1);}
} 板子 tips:
