手写加强堆

不了解堆结构的同学请先移步《堆与堆排序》

什么是加强堆？
我们现在知道，堆结构主要用来处理海量数据下的动态优先级问题，需要频繁入队和频繁把优先级最高的元素出队。但有一种情形是普通堆结构难以高效处理的：一旦堆中的数据发生改变，如果不维护，此堆将作废无法使用；如果维护，那么定位发生变动的元素所需要的时间复杂度就为 O(N)（即遍历整个堆），其性能变得低效。为了应对堆中数据可能发生改变的情况，加强堆闪亮登场。

加强堆与普通堆的不同之处在于：加强堆使用了一张哈希表来记录元素及其所在位置。当元素发生变动时，可以由这张表快速定位到所在位置，从而进行相应调整。注意，哈希表的键为元素，值为数组下标；而数组本身也是一张索引表，数组下标是索引，数组内容则是元素。

由于 STL 库没有自带的加强堆，所以我们自己丰衣足食，动手写一个模版吧。

#include<unordered_map>
#include<iostream>
#include<vector>
using std::vector;
using std::unordered_map;
using std::unordered_multimap;

template<class T>
struct maxHeap //大根堆的比较器
{
    bool operator()(const T &a, const T &b){
        return a < b;
    }
};

template<class T, class compare = maxHeap<T>>//模仿stl的普通堆,比较器默认大根堆
class heapGreater
{
private:
    vector<T> heap; //堆结构的底层容器
    unordered_multimap<T, int> indexMap; //反向索引表,注意是multimap,允许多个相同的键
    compare cmp; //比较器
    int count;
private:
    void swap(T& a,T& b);
    void heapInsert(int cur);
    void heapify(int cur);
public:
    heapGreater(){count = 0;}
    T pop();
    void push(const T &var);
    void remove(const T &var);
    void modify(const T &var1, const T &var2);
    T peek() {return heap[0];}
    int size() {return heap.size();}
    bool empty(){return count == 0;}
};

template<class T, class compare>
void heapGreater<T, compare>::swap(T& a,T& b)
{
    T tmp = a;
    a = b;
    b = tmp;
    
    //交换a,b在堆中的物理位置时,map中的索引也必须交换
    tmp = indexMap.find(a)->first;
    indexMap.find(a)->second = indexMap.find(b)->second;
    indexMap.find(b)->second = indexMap.find(tmp)->second;
}

template<class T, class compare>
void heapGreater<T, compare>::heapInsert(int cur)
{
    //假设cmp是<才交换,那么当父<子时,交换,即大值往上跑,也就是大根堆
    //相反,cmp是>时则为小根堆
    if (cmp(heap[(cur - 1) / 2], heap[cur]))
    {
        swap(heap[(cur - 1) / 2], heap[cur]);
        heapInsert((cur - 1) / 2);
    }
}

template<class T, class compare>
void heapGreater<T, compare>::heapify(int cur)
{
    int leftChd = cur * 2 + 1;
    if (leftChd > ((int)heap.size() - 1))//heap.size()返回的是无符号数size_t，若返回0，减1后为最大正数
        return;                          //所以必须要强制转为int!!!!!!!!!!!
    int mIndex;
    if(leftChd + 1 < (int)heap.size())//如存在右孩子,则选出左孩子与右孩子中最大(最小)的那个
        mIndex = cmp(heap[leftChd + 1], heap[leftChd]) ? leftChd + 1 : leftChd;
    else//如果没有右孩子,则直接选定左孩子
        mIndex = leftChd;
    if (cmp(heap[cur], heap[mIndex]))
    {
        swap(heap[mIndex], heap[cur]);
        heapify(mIndex);
    }
}

template<class T, class compare>
void heapGreater<T, compare>::push(const T &var)
{
    heap.push_back(var);
    indexMap.emplace(var,heap.size()-1);
    heapInsert(heap.size() - 1);
    count++;
}

template<class T, class compare>
T heapGreater<T, compare>::pop()
{
    T tmp = peek();
    swap(heap[0], heap[heap.size() - 1]);
    indexMap.erase(heap[heap.size()-1]);
    heap.pop_back();
    heapify(0);
    count--;
    return tmp;
}

template<class T, class compare>
void heapGreater<T, compare>::remove(const T &var) 
{
    int index = indexMap.find(var)->second;
    swap(heap[index], heap[heap.size() - 1]);
    indexMap.erase(heap[heap.size() - 1]);
    heap.pop_back();
    if (index != heap.size())//当要删除的元素位于堆末尾时，pop后不再做以下操作，否则越界。
    {                        //注意此处是已经pop后的，易错写为heap.size()-1
        heapify(index);
        heapInsert(index);//调整堆结构,两个中只会执行其中一个
    }
    count--;
}

template<class T, class compare>
void heapGreater<T, compare>::modify(const T &var1, const T &var2)
{
    int index = indexMap.find(var1)->second;
    heap[index] = var2;
    indexMap.erase(var1);//注意,本行和下面一行不可交换位置,原因见后文
    indexMap.emplace(var2, index);
    heapify(index);//调整堆结构,heapify与heapInsert中只会执行其中一个
    heapInsert(index);
}

结合之前的堆与堆排序文章和代码中的注释，应该就可以清楚地说明加强堆的结构和相关操作了。唯一要说明的是第 123、124 行代码，为什么不能交换这两行代码呢？因为 var1 和 var2 完全可以是同一个对象（当我仅修改了对象的值而非替换该对象，就会是这种情况），如果先加入 var2 ，那么 map 中就会有两个相同的键，当你随后 erase 时，你就不知道擦除的是你之前的对象，还是后加入的对象。

加强堆会应用在后续的topK问题和Dijsktra算法中。

本文结束。