C++基礎算法基于哈希表的索引堆變形
問題來源
此題來自于Hackerrank中的QHEAP1問題，考查了對堆結構的充分理解。成功完成此題，對最大堆或者最小堆的基本操作實現(xiàn)就沒什么太大問題了。
問題簡述
實現(xiàn)一個最小堆，對3種類型的輸入能給出正確的操作：
- “1 v” - 表示往堆中增加一個值為v的元素
- “2 v” - 表示刪去堆中值為v的元素
- “3” - 表示打印出堆中最小的那個元素
注意：題目保證了要刪的元素必然是在堆中的，并且在任何時刻，堆中不會有重復的元素。
輸入格式：
第1行的值表示共有q個操作，然后再接下來的q行中，每行都有上述3中操作中的任意一種。
比如：
******************輸入*******************
5
1 4
1 9
3
2 4
3
******************輸出*******************
4
9
問題分析
對于一個最小堆來說，其滿足的性質是只要每個子樹中的父親節(jié)點的元素小于其左孩子節(jié)點和右孩子節(jié)點的元素即可，比如下圖所示的這樣：
圖1：最小堆示例圖
沒錯，最小堆根部的元素必然是樹中最小的那個元素。除了滿足上述的條件之外，最小堆還必須是一顆完全二叉樹。也正是由于這個完全二叉樹的性質，最小堆是可以用數(shù)組來實現(xiàn)的，比如上圖的這個最小堆就可以表示成
data = { 5, 8, 20, 10, 35, 12, 50, 15, 16 };
從樹結構中不難看出索引之間有關系
這是我們在更新堆信息時最重要的公式，第3個式子的除法是取整的，所以左右孩子都一樣。
如果只需要滿足操作”1 v”和操作”3”的話，上述這些就已經(jīng)完全夠用了，難點在于這里需要我們對堆中指定的元素進行刪除”2 v”。講道理，這并不是一個最小堆所應該有的操作，最小堆只要管住最小的那個值就好了，其他的結構怎么樣，最小堆并不關心。不過，既然題目故意這么出了，要來刁難我們，我們也只能迎難而上了。
借助于索引堆的想法，我們用一個哈希表來記錄每一個元素在堆中的索引位置，這樣，我們在刪除時只需要 O(1) 的復雜度就可以找到要刪除的元素了，而刪除的過程是 O(log(n)) 的復雜度。
還是以上面那組數(shù)據(jù)為例，我們希望記錄的是如下的信息。
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_map>
using namespace std;
class myHeap{
private:
//作為堆的數(shù)組
vector<int> data;
//用于存放<元素值，在堆中的索引>的哈希表
unordered_map<int, int> mp;
//堆中元素的個數(shù)
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;
}
else
break;
}
return;
}
//下移操作，將元素大的順著樹結構往下移
void _shiftDown(int index){
if (index >= size || index < 0)
return;
while (index * 2 + 1 < size){
int newIndex = index * 2 + 1;
//選擇左節(jié)點和右節(jié)點中比較小的那個元素
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();
}
}
}
如有不足，還請指正~
以上就是C++基礎算法基于哈希表的索引堆變形的詳細內容，更多關于C++算法哈希表索引堆變形的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單三子棋程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要為大家詳細介紹了使用C語言實現(xiàn)三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
下面小編就為大家?guī)硪黄狢語言實現(xiàn)用戶態(tài)線程庫案例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要詳細講解了C++數(shù)據(jù)封裝以及定義結構，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-05-05
線性表的鏈式存儲特點則是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的。本文將詳解一下C語言線性表的鏈式表示及實現(xiàn)，感興趣的可以了解一下2022-07-07
這篇文章主要介紹了C語言中的程序環(huán)境與預處理詳情，文章圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的朋友可以參考一下2022-07-07
本文主要介紹了拷貝構造函數(shù)和賦值運算符的區(qū)別，以及在什么時候調用拷貝構造函數(shù)、什么情況下調用賦值運算符。最后，簡單的分析了下深拷貝和淺拷貝的問題。有需要的朋友可以看下2016-12-12
這篇文章主要為大家詳細介紹了C語言編寫學生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
C++20 是 C++ 語言的一次重大更新,它引入了許多新特性,本文主要介紹了淺談C++20新增內容,具有一定的參考價值,感興趣的可以了解一下2025-04-04
以下是對函數(shù)指針與返回函數(shù)的指針進行了詳細的分析介紹，需要的朋友可以過來參考下2013-07-07