堆的操作_编写代码,实现最小堆(min-heap)的操作。 输入格式: 第一行是两个不大于1000的正整-程序员宅基地

技术标签: # PTA基础编程题目集  

编写代码,实现最小堆(Min-Heap)的操作。

输入格式:

第一行是两个不大于1000的正整数NK,用空格间隔。其中N是堆的容量,需创建一个容量为N的堆。

接下来K行,是对这个堆的依次的K项插入或删除操作:用 1 x 表示插入元素x;用 -1 表示删除堆顶。

接下来一行是一个不大于1000的正整数M

接下来一行是M个整数(在整型范围内),用空格间隔,

要求将这M个整数组成的列表调整为一个最小堆。

输出格式:

对于第一个堆的K项操作,每次操作后,在一行中依次序打印堆元素,元素间使用1个空格分隔;

对于第二个堆,在调整完成后,在一行中依次序打印堆元素,元素间使用1个空格分隔。

输入样例:

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

输出样例:

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
2 4 3 5
2 4 3 5 6
3 4 6 5
1 2 3 4 5 6 7 8
#include<iostream>

using namespace std;

struct heap{
	int data[1001];
	int size;
	int capacity;
	heap(int cap){
		size = 0;
		capacity = cap;
	}
};

typedef struct heap* Heap;

void percolateUp(Heap h, int index){
	int i, tmp = h->data[index];
	for(i = index; i / 2 > 0 && tmp < h->data[i / 2]; i /= 2)
		h->data[i] = h->data[i / 2];
	h->data[i] = tmp;
}

void percolateDown(Heap h, int index){
	int i, tmp = h->data[index], child;
	for(i = index; i * 2 <= h->size; i = child){
		child = i * 2;
		if(child < h->size && h->data[child + 1] < h->data[child]) child++;
		if(tmp > h->data[child]) h->data[i] = h->data[child];
		else break;
	}
	h->data[i] = tmp;
}

void insert(Heap h, int key){
	if(h->size == h->capacity) return ;
	h->data[++h->size] = key;
	percolateUp(h, h->size);
}

void remove(Heap h){
	if(h->size == 0) return ;
	h->data[1] = h->data[h->size];
	h->size--;
	percolateDown(h, 1);
}

void print(Heap h){
	for(int i = 1; i < h->size; i++)
		cout << h->data[i] << ' ';
	cout << h->data[h->size] << endl;
}

int main(){
	int N, K, M;
	int tmp;
	cin >> N >> K;
	Heap h = new heap(N);
	for(int i = 0; i < K; i++){
		cin >> tmp;
		if(tmp == 1){
			cin >> tmp;
			insert(h, tmp);
		}else{
			remove(h);
		}
		print(h);
	}
	cin >> M;
	Heap h2 = new heap(1001);
	for(int i = 0; i < M; i++){
		cin >> tmp;
		h2->data[++h2->size] = tmp;
	}
	for(int i = h2->size / 2; i > 0; i--){
		percolateDown(h2, i);
	}
	print(h2);
	return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/LightInDarkness/article/details/104519570

智能推荐

ubuntu20.04安装配置VNC远程桌面_ubuntu安装vnc远程桌面-程序员宅基地

文章浏览阅读1.4k次。Ubuntu20.04配置VNC远程桌面_ubuntu安装vnc远程桌面

用CocoaPods做iOS程序的依赖管理_ios 依赖cocoapods-程序员宅基地

文章浏览阅读401次。文章目录1.文档更新说明2.CocoaPods 简介3.CocoaPods 的安装和使用介绍3.1.安装3.2.使用 CocoaPods 的镜像索引3.3.使用 CocoaPods3.4.查找第三方库3.5.关于 Podfile.lock4.为自己的项目创建 podspec 文件5.使用私有的 pods6.不更新 podspec_ios 依赖cocoapods

caffe学习笔记1源码阅读步骤_如何有效阅读caffe源码-程序员宅基地

文章浏览阅读153次。caffe学习笔记1:源码阅读步骤本文系转载,原文地址 https://ymgd.github.io/codereader/201..._如何有效阅读caffe源码

poj-1699-Best Sequence-dfs+子状态_1161142536-程序员宅基地

文章浏览阅读1k次。这道题目竟然真的ac了,好神奇啊。当时算的时间复杂度为O(T*N!),理论值达到7kw。做法:预处理dp数组,使得dp[i][j]代表j放在i后面长度的增加值。然后dfs,dfs的时候要注意,用一个二进制数标记当前状态。二进制中0代表当前位置已取,1代表当前位置未取。每次查找二进制的子状态。然后看看哪个位置在子状态消失了。一定要直接查找子状态。查找方法详参我的另一篇_1161142536

第四篇:mmpose之各类Demo测试及自定义数据原理(强推)-程序员宅基地

文章浏览阅读4k次,点赞5次,收藏9次。博主本人做关键点检测的思路主要是Top-down,即先用检测算法得到目标框,在用mmpose里的网络得到关键点坐标并可视化。那么如果我们想用自己的检测网络,那么怎么和MMpose整合到一起呢?首先要做的第一步是得把官方Demo跑通,下面将会分别以2D人体图像关键点检测、2D人体图像全身关键点检测,2D动物图像关键点检测、2D面部图像关键点检测、3D人体分割、3D手部关键点检测、3D姿态估计的顺序,分别教大家如何用自己的数据、通过标注制作数据集实现官方Demo的跑通。第一节:2D人体图像关键点检测_mmpose之各类demo测试及自定义

RedrawWindow 和 InvalidateRect 刷新_redrawwindow与invalidaterect-程序员宅基地

文章浏览阅读1k次。当父窗体设置了 WS_CLIPCHILDREN 的属性后, 默认状态下,RedrawWindow 和 InvalidateRect 不会导致子窗体重绘,因此,如果子窗体同时设置了 WS_EX_TRANSPARENT 属性,子窗体就会被父窗体刷没了。解决的办法是 RedrawWindow 的时候添加 RDW_ALLCHILDREN 标志,强制子窗体也重绘,而不要使用默认的 RedrawWindow 和 InvalidateRect(当然也包括 Invalidate)。Red_redrawwindow与invalidaterect

随便推点

《Linux多线程muduo》读书笔记2——如何从零开始写一个日志_linux 多线程写日志-程序员宅基地

文章浏览阅读259次。从零开始写一个日志工具本文主要将muduo中的日志库剥离下来,挑选出关键的东西,给大家在写自己的日志工具时候提供一些思路。文章目录从零开始写一个日志工具1. 版本11.1 思路1.2 源代码2. 版本22.1 设置日志工具的全局级别1. 版本11.1 思路在构造函数中根据日志级别完成format重载operator <<,将一句话中的多条日志信息append到buffer..._linux 多线程写日志

Fedora22 下移植opencv-2.4.10_依赖关系解决。 无需任何处理。 完毕!-程序员宅基地

文章浏览阅读1k次。在Fedora22下移植opencv-2.4.10首先到官网或其他地方获取opencv-2.4.10。在opencv-2.4.10里面已经包含了cmake了,等会直接用就可以。在Fedora22下安装编译环境,因为这些操作我已经做完,所以下面都显示跳过。一、安装编译环境:[root@localhost cpp]# dnf install gcc gcc-c++ ncurse_依赖关系解决。 无需任何处理。 完毕!

国科大人工智能学院《计算机视觉》课 —三维视觉—三维表达与语义建模_ai 语义 三维建模-程序员宅基地

文章浏览阅读705次,点赞4次,收藏8次。一、三维建模的方式:SFM+MVS、X(明暗、光度立体、纹理、焦点)二、点云网格建模1. 小场景的点云网格化算法2. 大场景的点云网格化算法:分布式点云网格化三、三维语义建模1. 三维语义分割:基于几何特征2. 三维语义分割:基于模板匹配3. 三维语义分割:端到端分割4. 二维图像分割的三维融合5. 语义和几何的联合优化四、三维矢量建模..._ai 语义 三维建模

GDAL影像重采样_c++使用gdal读取,对影像下采样-程序员宅基地

文章浏览阅读5.9k次,点赞4次,收藏21次。学习过程中,用到重采样,感觉不错,转载过来供大家学习,原文地址:http://blog.csdn.net/giselite/article/details/7792620 #include "gdal_priv.h" #include "ogrsf_frmts.h" #include "gdalwarper.h" /*** _c++使用gdal读取,对影像下采样

LeetCode刷题复盘笔记—一文搞懂0 - 1背包之494. 目标和问题(动态规划系列第九篇)_0-1背包目标和-程序员宅基地

文章浏览阅读855次。LeetCode刷题复盘笔记—一文搞懂0 - 1背包之494. 目标和问题(动态规划系列第九篇)运算结果等于 target 的不同 表达式 的数目。示例 1:输入:nums = [1,1,1_0-1背包目标和

图片上传(方法一:jquery.upload.js)-程序员宅基地

文章浏览阅读4.6k次。一、在JSP页面引入jquery.upload.js 文件:<script type="text/javascript" src="${ctx}/script/jquery.upload.js"></script>二、JSP页面代码:<!-- 弹窗 开始 --> <div class="dialog_teachermanage" id=..._upload.js

推荐文章

热门文章

相关标签