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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<unordered_map>
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

class heapGreater
{
private:
	vector<int> heap;
	unordered_multimap<int, int> indexMap;
private:
	void swap(int& a,int& b) {
		int tmp = a;
		a = b;
		b = tmp;
		tmp = indexMap.find(a)->second;
		indexMap.find(a)->second = indexMap.find(b)->second;
		indexMap.find(b)->second = tmp;
	}

	void heapInsert(int cur){
		if (heap[(cur - 1) / 2] < heap[cur])//大顶堆
		{
			swap(heap[(cur - 1) / 2], heap[cur]);
			heapInsert((cur - 1) / 2);
		}
	}
	void heaplify(int cur)
	{
		int leftChd = cur * 2 + 1;
		if (leftChd > ((int)heap.size() - 1))//heap.size()返回的是无符号数size_t，若返回0，减1后为最大正数
			return;                          //所以必须要强制转为int
		int largest = leftChd + 1 < (int)heap.size() && heap[leftChd + 1] > heap[leftChd] ? leftChd + 1 : leftChd;
		if (heap[largest] > heap[cur])//大堆顶
		{
			swap(heap[largest], heap[cur]);
			heaplify(largest);
		}
	}

public:
	void push(int var) {
		if (indexMap.find(var) != indexMap.end())//不能加重复值！这是本实现的局限性
			return;
		heap.push_back(var);
		indexMap.emplace(var,heap.size()-1);
		heapInsert(heap.size() - 1);
	}

	int size() {
		return heap.size();
	}

	int peek() {
		return heap[0];
	}

	void pop() {
		swap(heap[0], heap[heap.size() - 1]);
		indexMap.erase(heap[heap.size()-1]);
		heap.pop_back();
		heaplify(0);
	}

	void remove(int var) {
		int index = indexMap.find(var)->second;
		swap(heap[index], heap[heap.size() - 1]);
		indexMap.erase(heap[heap.size() - 1]);//参数可以直接写var
		heap.pop_back();
		if (index != heap.size())//！当要删除的元素位于堆末尾时，pop后不再做以下操作，否则越界。注意此处是已经pop后的，易错写为heap.size()-1
		{
			heaplify(index);
			heapInsert(index);//两个只会执行其中一个
		}
	}

	void modify(int var1, int var2)
	{
		if (var1 == var2)
			return;
		int index = indexMap.find(var1)->second;
		heap[index] = var2;
		indexMap.emplace(var2, index);
		indexMap.erase(var1);
		heaplify(index);
		heapInsert(index);		
	}

};
int main()
{
	heapGreater shit;
	shit.push(5);
	shit.push(10);
	shit.push(4);
	shit.push(1);
	shit.push(32);
	shit.push(50);
	shit.push(60);
	shit.modify(10, 121);
	shit.remove(32);
	while (shit.size() != 0)
	{
		cout << shit.peek() << " ";
		shit.pop();
	}
}