wordpress建博客网站,江西省城乡建设厅网站证件查询,没有经验可以做新媒体运营吗,如何用织梦cms做网站问题来源
此题来自于Hackerrank中的QHEAP1问题#xff0c;考查了对堆结构的充分理解。成功完成此题#xff0c;对最大堆或者最小堆的基本操作实现就没什么太大问题了。
问题简述
实现一个最小堆#xff0c;对3种类型的输入能给出正确的操作#xff1a;
“1 v” - 表示往…问题来源
此题来自于Hackerrank中的QHEAP1问题考查了对堆结构的充分理解。成功完成此题对最大堆或者最小堆的基本操作实现就没什么太大问题了。
问题简述
实现一个最小堆对3种类型的输入能给出正确的操作
“1 v” - 表示往堆中增加一个值为v的元素“2 v” - 表示删去堆中值为v的元素“3” - 表示打印出堆中最小的那个元素
注意题目保证了要删的元素必然是在堆中的并且在任何时刻堆中不会有重复的元素。 输入格式 第1行的值表示共有q个操作然后再接下来的q行中每行都有上述3中操作中的任意一种。 比如
******************输入*******************
5
1 4
1 9
3
2 4
3
******************输出*******************
4
9
问题分析
对于一个最小堆来说其满足的性质是只要每个子树中的父亲节点的元素小于其左孩子节点和右孩子节点的元素即可比如下图所示的这样 图1最小堆示例图没错最小堆根部的元素必然是树中最小的那个元素。除了满足上述的条件之外最小堆还必须是一颗
完全二叉树。也正是由于这个完全二叉树的性质最小堆是可以用数组来实现的比如上图的这个最小堆就可以表示成data { 5, 8, 20, 10, 35, 12, 50, 15, 16 };
从树结构中不难看出索引之间有关系
⎧⎩⎨leftChild2⋅parent1rightChild2⋅parent2parent(child−1)/2\begin{cases}leftChild = 2 \cdot parent + 1 \\ rightChild = 2 \cdot parent + 2 \\ parent = (child - 1) / 2\end{cases}这是我们在更新堆信息时最重要的公式第3个式子的除法是取整的所以左右孩子都一样。 如果只需要满足操作”1 v”和操作”3”的话上述这些就已经完全够用了难点在于这里需要我们对堆中指定的元素进行删除”2 v”。讲道理这并不是一个最小堆所应该有的操作最小堆只要管住最小的那个值就好了其他的结构怎么样最小堆并不关心。不过既然题目故意这么出了要来刁难我们我们也只能迎难而上了。 借助于索引堆的想法我们用一个哈希表来记录每一个元素在堆中的索引位置这样我们在删除时只需要O(1)O(1)的复杂度就可以找到要删除的元素了而删除的过程是O(log(n))O(log(n))的复杂度。 还是以上面那组数据为例我们希望记录的是如下的信息。data { 5, 8, 20, 10, 35, 12, 50, 15, 16 };
mp {{20, 2}, {35, 4}, {8, 1}, {5, 0}, {16, 8}, {50, 6}, {12, 5}, {10, 3}, {15, 7}};
哈希表中元素的顺序完全无所谓只要元素中的对应关系正确即可所以上面的这个是我乱编的具体的顺序和插入元素的顺序有关系。
代码展示
最后来展示一下完整的代码把下面这个代码直接复制粘贴到题目中去Submit是没问题的。
#include vector
#include iostream
#include unordered_mapusing namespace std;class myHeap{
private://作为堆的数组vectorint data;//用于存放元素值在堆中的索引的哈希表unordered_mapint, int mp;//堆中元素的个数int size;private://上移操作将元素小的顺着树结构往上移void _shiftUp(int index){if (index size || index 0)return;while (index ! 0){int newIndex (index - 1) / 2;if (data[newIndex] data[index]){//更新哈希表中存放的索引mp[data[newIndex]] index;mp[data[index]] newIndex;//更新堆中元素的位置swap(data[newIndex], data[index]);index newIndex;}elsebreak;}return;}//下移操作将元素大的顺着树结构往下移void _shiftDown(int index){if (index size || index 0)return;while (index * 2 1 size){int newIndex index * 2 1;//选择左节点和右节点中比较小的那个元素if (newIndex 1 size data[newIndex 1] data[newIndex])newIndex;if (data[newIndex] data[index])break;//更新哈希表中存放的索引mp[data[newIndex]] index;mp[data[index]] newIndex;//更新堆中元素的位置swap(data[newIndex], data[index]);index newIndex;}return;}public:myHeap(){size 0;}//添加元素void add(int d){data.push_back(d);mp[d] size;_shiftUp(mp[d]);}//删除元素void del(int d){int index mp[d];mp[d] size - 1;mp[data[size - 1]] index;swap(data[index], data[size - 1]);size--;data.pop_back();_shiftUp(index);_shiftDown(index);mp.erase(d);}//打印堆中最小值void showMin(){cout data[0] endl;}
};int main() {/* Enter your code here. Read input from STDIN. Print output to STDOUT */int q;cin q;myHeap h;for (int i 0; i q; i){int index;cin index;if (index 1){int v;cin v;h.add(v);}else if (index 2){int v;cin v;h.del(v);}else if (index 3){h.showMin();}}
}
如有不足还请指正~
