将一系列给定数字顺序插入一个初始为空的小顶堆H[]
随后判断一系列相关命题是否为真。命题分下列几种:
每组测试第1行包含2个正整数N
(≤ 1000)和M
(≤ 20)分别是插入元素嘚个数、以及需要判断的命题数。下一行给出区间[?]内的N
个要被插入一个初始为空的小顶堆的整数之后M
行,每行给出一个命题题目保證命题中的结点键值都是存在的。
对输入的每个命题如果其为真,则在一行中输出T
否则输出F
。
小顶堆:是一种经过排序的完全二叉树(树的节点是按从上到下从左到右的顺序紧凑排列的),其中任一非终端节点的数据值均不大于其左子节点和右子节点的值
若从heap[0]开始存,可知:
左儿子编号是自己编号*2+1
右儿子编号是自己编号*2+2
首先先在堆的末尾(在最后一层最左边)插入该数值,然後不断向上提升至到它比父节点大为止
先把堆中最后一个元素复制到根节点,并且删除最后一个节点然后不断姠下交换直到没有大小点到为止。
若向下交换的时候左右节点都小于此节点,则交换最小的节点
while(i*2+1<sz){//点i位置存在左子树即可,因为可能本來就不存在右子树
ps:处理的时候别忘了还有负数的情况哒~
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。