C++基礎(chǔ)算法基于哈希表的索引堆變形

更新時(shí)間：2021年10月12日 12:01:04 作者：zjuPeco

這篇文章主要為大家介紹了C++基礎(chǔ)算法，基于哈希表的索引堆變形示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步

問題來源

此題來自于Hackerrank中的QHEAP1問題，考查了對堆結(jié)構(gòu)的充分理解。成功完成此題，對最大堆或者最小堆的基本操作實(shí)現(xiàn)就沒什么太大問題了。

問題簡述

實(shí)現(xiàn)一個(gè)最小堆，對3種類型的輸入能給出正確的操作：

“1 v” - 表示往堆中增加一個(gè)值為v的元素
“2 v” - 表示刪去堆中值為v的元素
“3” - 表示打印出堆中最小的那個(gè)元素

注意：題目保證了要?jiǎng)h的元素必然是在堆中的，并且在任何時(shí)刻，堆中不會有重復(fù)的元素。
輸入格式：
第1行的值表示共有q個(gè)操作，然后再接下來的q行中，每行都有上述3中操作中的任意一種。
比如：

******************輸入*******************
5
1 4
1 9
3
2 4
3
******************輸出*******************
4
9

問題分析

對于一個(gè)最小堆來說，其滿足的性質(zhì)是只要每個(gè)子樹中的父親節(jié)點(diǎn)的元素小于其左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)的元素即可，比如下圖所示的這樣：

最小堆

圖1：最小堆示例圖

沒錯(cuò)，最小堆根部的元素必然是樹中最小的那個(gè)元素。除了滿足上述的條件之外，最小堆還必須是一顆完全二叉樹。也正是由于這個(gè)完全二叉樹的性質(zhì)，最小堆是可以用數(shù)組來實(shí)現(xiàn)的，比如上圖的這個(gè)最小堆就可以表示成

data = { 5, 8, 20, 10, 35, 12, 50, 15, 16 };

從樹結(jié)構(gòu)中不難看出索引之間有關(guān)系

這是我們在更新堆信息時(shí)最重要的公式，第3個(gè)式子的除法是取整的，所以左右孩子都一樣。
如果只需要滿足操作”1 v”和操作”3”的話，上述這些就已經(jīng)完全夠用了，難點(diǎn)在于這里需要我們對堆中指定的元素進(jìn)行刪除”2 v”。講道理，這并不是一個(gè)最小堆所應(yīng)該有的操作，最小堆只要管住最小的那個(gè)值就好了，其他的結(jié)構(gòu)怎么樣，最小堆并不關(guān)心。不過，既然題目故意這么出了，要來刁難我們，我們也只能迎難而上了。
借助于索引堆的想法，我們用一個(gè)哈希表來記錄每一個(gè)元素在堆中的索引位置，這樣，我們在刪除時(shí)只需要 O(1) 的復(fù)雜度就可以找到要?jiǎng)h除的元素了，而刪除的過程是 O(log(n)) 的復(fù)雜度。
還是以上面那組數(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}};

哈希表中元素的順序完全無所謂，只要元素中的對應(yīng)關(guān)系正確即可，所以上面的這個(gè)是我亂編的，具體的順序和插入元素的順序有關(guān)系。

代碼展示

最后，來展示一下完整的代碼，把下面這個(gè)代碼直接復(fù)制粘貼到題目中去Submit是沒問題的。

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
class myHeap{
private:
    //作為堆的數(shù)組
    vector<int> data;
    //用于存放<元素值，在堆中的索引>的哈希表
    unordered_map<int, int> mp;
    //堆中元素的個(gè)數(shù)
    int size;
private:
    //上移操作，將元素小的順著樹結(jié)構(gòu)往上移
    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;
    }

    //下移操作，將元素大的順著樹結(jié)構(gòu)往下移
    void _shiftDown(int index){
        if (index >= size || index < 0)
            return;
        while (index * 2 + 1 < size){
            int newIndex = index * 2 + 1;
            //選擇左節(jié)點(diǎn)和右節(jié)點(diǎn)中比較小的那個(gè)元素
            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++基礎(chǔ)算法基于哈希表的索引堆變形的詳細(xì)內(nèi)容，更多關(guān)于C++算法哈希表索引堆變形的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: