【体系学习007】加强堆

Posted by Hilda on September 24, 2025

1.通过规模和指令条数来推测算法复杂度

在线评测系统需要一个公平的环境来评估不同语言的解法。考虑到 Java 特有的启动和 JIT 开销,如果将所有语言的时间限制都设为 1-2 秒(C/C++通常是这样),那么一些本应通过的 Java 代码可能会因为这些“系统开销”而超时。

为了弥补这种天生的劣势,评测系统会为 Java 这类需要虚拟机的语言提供更宽裕的时间限制(比如2-4秒),以确保竞赛的公平性。这个时间差通常是根据经验值和大量测试得出的,旨在让参赛者能专注于算法本身的效率,而不是语言特性带来的额外负担。

考虑这样的已知条件:

  • 评测系统的大致时间限制:1秒
  • 1秒大致能执行的指令数:\(10^8\) 条
  • 输入数据的规模(比如数组大小):\(N=10^3\)

现在一道算法题的要求是:找到一个算法复杂度(比如 \(O(N^2)\)、\(O(NlogN)\)、\(O(N^3)\) 等),使得当 \(N=10^3\) 时,总运算量不超过 \(10^8\)。

那么大概率需找到一个\(O(N^2)\) 或更优(比如 O(NlogN))的解法,那么这个算法大概率能在规定时间内通过。(显然O(\(N^3\))不太行)

总而言之,这种通过规模反推复杂度的方法,是算法竞赛中非常实用的一个技巧,它能帮助你快速筛选出可行的解法,避免在错误的思路上浪费时间。

2.最大线段重合问题(用堆的实现)

【思路】:任何重合区域的左边界一定是某个线段的左边界,所以考察每个线段的左边界,到底有多少重合线段。

【解法】:

  • 首先,对所有线段按照它们的左边界进行升序排序。
  • 使用最小堆跟踪结束点: 创建一个最小堆 heap,用于存放当前所有正在进行的线段的结束点。

  • 遍历线段: 检查堆顶元素 heap.peek(),如果堆顶元素的结束点小于或等于当前线段的起始点 lines[i][0],说明该线段已经结束了,不再与当前线段重叠。将它从堆中移除 (poll())。不断重复此操作,直到堆顶的结束点晚于当前线段的起始点。

  • 添加新的线段: 将当前线段的结束点 lines[i][1] 添加到堆中。

  • 更新最大重叠数: 在每一步操作后,堆中剩余的元素数量就是当前时间点上正在进行的线段数量。用一个变量 ans 记录下堆的最大容量 heap.size(),这个值就是最多同时重叠的线段数量。

【时间复杂度】 O(NlogN),主要是由排序和堆的操作决定的。

【额外空间复杂度】 O(N),Java 的 Arrays.sort() 方法在对对象数组进行排序时,通常需要一个大小为 O(N) 的额外空间作为辅助数组;另外PriorityQueue,在最坏的情况下,所有线段都可能在某一时刻重叠。此时,最小堆需要存储所有 N 个线段的结束点,因此其空间复杂度是 O(N)。

试题链接(ACM风格,线段重合):https://www.nowcoder.com/practice/1ae8d0b6bb4e4bcdbf64ec491f63fc37

解法:

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
import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;
            in.nextToken();
            int[][] lines = new int[n][2];
            for (int i = 0;i < n;i++) {
                lines[i][0] = (int)in.nval;
                in.nextToken();
                lines[i][1] = (int)in.nval;
                in.nextToken();
            }
            int ans = get(lines);
            out.println(ans);
        }
        out.flush();
        br.close();
        out.close();
    }

    public static int get(int[][] lines) {
        int ans = 0;
        Arrays.sort(lines, (a, b)->(a[0]-b[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0;i < lines.length;i++) {
            while (heap.size() > 0 && heap.peek() <= lines[i][0]) {
                heap.poll();
            }
            heap.add(lines[i][1]);
            ans = Math.max(ans, heap.size());
        }

        return ans;
    }
}

3.手动改写堆(加强堆)

3.1原理

系统提供的堆无法做到的事情: 1)已经入堆的元素,如果参与排序的指标方法变化, 系统提供的堆无法做到时间复杂度O(logN)调整!都是O(N)的调整! 2)系统提供的堆只能弹出堆顶,做不到自由删除任何一个堆中的元素, 或者说,无法在时间复杂度O(logN)内完成!一定会高于O(logN) 根本原因:无反向索引表

举个例子:假设你有一个对象Student,它根据score属性值入堆。当你改变了某个学生的score后,PriorityQueue并不知道这个学生在堆的哪个位置。为了找到它,你必须遍历整个堆,这需要O(N)的时间。找到后,你才能将其删除(O(N))并重新插入(O(logN)),总时间复杂度为O(N)。

如果你需要频繁地对堆中元素的排序指标进行更新,并希望保持O(logN)的性能,那么你需要自己实现一个带反向索引表的数据结构。例如,可以使用一个HashMap来存储元素 -> 数组索引的映射关系。

Java不直接提供一个内置的、带反向索引表的堆(如java.util.PriorityQueue),主要是基于以下几个原因:

1.设计哲学与通用性

PriorityQueue的设计目标是提供一个基础、高效的优先级队列实现。在绝大多数应用场景中,优先级队列的核心操作就是插入元素add)和移除最高优先级元素poll)。对于这些基本操作,PriorityQueue已经通过二叉堆结构做到了最优的时间复杂度(O(logN))。

加入反向索引表(如HashMap)会带来额外的开销,包括:

  • 内存开销:每个元素都需要在HashMap中存储一份额外的引用和哈希值,这会增加堆的内存占用。
  • 性能开销:每次插入、删除或更新元素时,不仅要维护堆结构,还要同步更新HashMap中的映射关系。虽然这些操作的理论时间复杂度不变,但在实际运行中,哈希表的维护(如哈希计算、冲突处理)会比单纯的数组操作慢。

标准库的设计者倾向于提供基础、高效且通用的数据结构。如果需要更复杂的功能(比如支持任意元素的高效删除或更新),开发者可以根据自己的需求,通过组合现有数据结构(如PriorityQueueHashMap)来构建。这种“组合优于继承”的设计思想,是Java乃至许多面向对象语言的核心原则。

2.避免复杂性与增加风险

一个内置的反向索引堆会变得更复杂。例如,它需要处理以下问题:

  • 键的唯一性:反向索引表需要一个唯一的键来映射到堆的索引。如果堆中包含重复元素,这个键的选择就变得复杂。例如,可能需要使用对象的引用作为键,但如果元素是可变的,哈希值也可能发生变化,这会破坏哈希表的完整性。
  • 线程安全PriorityQueue本身不是线程安全的。如果加入了反向索引表,同步机制会变得更加复杂,以确保堆和哈希表的数据一致性。

将这种复杂性交给开发者,让他们根据具体应用场景来决定是否需要,是一种更灵活、更安全的方式。

3.性能不是唯一考量

在许多场景下,$O(N)$的性能开销是可以接受的。例如,如果你只是偶尔需要更新或删除某个特定元素,那么为了这个不频繁的操作而牺牲整体的内存和性能,可能是不划算的。

总而言之,Java标准库的设计哲学是提供最小化功能强大的构建块。PriorityQueue作为一个高效的优先级队列已经足够。开发者如果需要高级功能,可以自行组合其他数据结构,从而实现按需定制,而不是被迫接受一个功能更全但可能更臃肿、更慢的内置实现。


这种设计思路也体现在许多其他标准库中,例如,Java的HashSetHashMap都基于哈希表,但它们的内部实现细节隐藏了起来,只暴露了简单、清晰的接口。这让开发者可以专注于解决问题,而不是纠结于底层实现。


手动改写堆:

  • 1)建立反向索引表
  • 2)建立比较器
  • 3)核心在于各种结构相互配合,非常容易出错

3.2题目-商品买又退

给定一个整型数组,int[] arr;和一个布尔类型数组,boolean[] op 两个数组一定等长,假设长度为N,arr[i]表示客户编号,op[i]表示客户操作 arr = [ 3 , 3 , 1 , 2, 1, 2, 5… op = [ T , T, T, T, F, T, F… 依次表示:3用户购买了一件商品,3用户购买了一件商品,1用户购买了一件商品,2用户购买了一件商品,1用户退货了一件商品,2用户购买了一件商品,5用户退货了一件商品…


一对arr[i]op[i]就代表一个事件: 用户号为arr[i],op[i] == T就代表这个用户购买了一件商品 op[i] == F就代表这个用户退货了一件商品 现在你作为电商平台负责人,你想在每一个事件到来的时候, 都给购买次数最多的前K名用户颁奖。 所以每个事件发生后,你都需要一个得奖名单(得奖区)。


得奖系统的规则: 1,如果某个用户购买商品数为0,但是又发生了退货事件, 则认为该事件无效,得奖名单和上一个事件发生后一致,例子中的5用户 2,某用户发生购买商品事件,购买商品数+1,发生退货事件,购买商品数-1 3,每次都是最多K个用户得奖,K也为传入的参数 如果根据全部规则,得奖人数确实不够K个,那就以不够的情况输出结果

4,得奖系统分为得奖区和候选区,任何用户只要购买数>0, 一定在这两个区域中的一个 5,购买数最大的前K名用户进入得奖区, 在最初时如果得奖区没有到达K个用户,那么新来的用户直接进入得奖区 6,如果购买数不足以进入得奖区的用户,进入候选区

7,如果候选区购买数最多的用户,已经足以进入得奖区, 该用户就会替换得奖区中购买数最少的用户(大于才能替换), 如果得奖区中购买数最少的用户有多个,就替换最早进入得奖区的用户 如果候选区中购买数最多的用户有多个,机会会给最早进入候选区的用户

8,候选区和得奖区是两套时间, 因用户只会在其中一个区域,所以只会有一个区域的时间,另一个没有 从得奖区出来进入候选区的用户,得奖区时间删除, 进入候选区的时间就是当前事件的时间(可以理解为arr[i]和op[i]中的i) 从候选区出来进入得奖区的用户,候选区时间删除, 进入得奖区的时间就是当前事件的时间(可以理解为arr[i]和op[i]中的i)

9,如果某用户购买数==0,不管在哪个区域都离开,区域时间删除, 离开是指彻底离开,哪个区域也不会找到该用户 如果下次该用户又发生购买行为,产生>0的购买数, 会再次根据之前规则回到某个区域中,进入区域的时间重记


请遍历arr数组和op数组,遍历每一步输出一个得奖名单

public List<List<Integer>> topK (int[] arr, boolean[] op, int k)

给出答案和对数器:

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
package class07;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class Code02_EveryStepShowBoss {

	public static class Customer {
		public int id;
		public int buy;
		public int enterTime;

		public Customer(int v, int b, int o) {
			id = v;
			buy = b;
			enterTime = 0;
		}
	}

	public static class CandidateComparator implements Comparator<Customer> {

		@Override
		public int compare(Customer o1, Customer o2) {
			return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
		}

	}

	public static class DaddyComparator implements Comparator<Customer> {

		@Override
		public int compare(Customer o1, Customer o2) {
			return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
		}

	}

	public static class WhosYourDaddy {
		private HashMap<Integer, Customer> customers;
		private HeapGreater<Customer> candHeap;
		private HeapGreater<Customer> daddyHeap;
		private final int daddyLimit;

		public WhosYourDaddy(int limit) {
			customers = new HashMap<Integer, Customer>();
			candHeap = new HeapGreater<>(new CandidateComparator());
			daddyHeap = new HeapGreater<>(new DaddyComparator());
			daddyLimit = limit;
		}

		// 当前处理i号事件,arr[i] -> id,  buyOrRefund
		public void operate(int time, int id, boolean buyOrRefund) {
			if (!buyOrRefund && !customers.containsKey(id)) {
				return;
			}
			if (!customers.containsKey(id)) {
				customers.put(id, new Customer(id, 0, 0));
			}
			Customer c = customers.get(id);
			if (buyOrRefund) {
				c.buy++;
			} else {
				c.buy--;
			}
			if (c.buy == 0) {
				customers.remove(id);
			}
			if (!candHeap.contains(c) && !daddyHeap.contains(c)) {
				if (daddyHeap.size() < daddyLimit) {
					c.enterTime = time;
					daddyHeap.push(c);
				} else {
					c.enterTime = time;
					candHeap.push(c);
				}
			} else if (candHeap.contains(c)) {
				if (c.buy == 0) {
					candHeap.remove(c);
				} else {
					candHeap.resign(c);
				}
			} else {
				if (c.buy == 0) {
					daddyHeap.remove(c);
				} else {
					daddyHeap.resign(c);
				}
			}
			daddyMove(time);
		}

		public List<Integer> getDaddies() {
			List<Customer> customers = daddyHeap.getAllElements();
			List<Integer> ans = new ArrayList<>();
			for (Customer c : customers) {
				ans.add(c.id);
			}
			return ans;
		}

		private void daddyMove(int time) {
			if (candHeap.isEmpty()) {
				return;
			}
			if (daddyHeap.size() < daddyLimit) {
				Customer p = candHeap.pop();
				p.enterTime = time;
				daddyHeap.push(p);
			} else {
				if (candHeap.peek().buy > daddyHeap.peek().buy) {
					Customer oldDaddy = daddyHeap.pop();
					Customer newDaddy = candHeap.pop();
					oldDaddy.enterTime = time;
					newDaddy.enterTime = time;
					daddyHeap.push(newDaddy);
					candHeap.push(oldDaddy);
				}
			}
		}

	}

	public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
		List<List<Integer>> ans = new ArrayList<>();
		WhosYourDaddy whoDaddies = new WhosYourDaddy(k);
		for (int i = 0; i < arr.length; i++) {
			whoDaddies.operate(i, arr[i], op[i]);
			ans.add(whoDaddies.getDaddies());
		}
		return ans;
	}

	// 干完所有的事,模拟,不优化
	public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
		HashMap<Integer, Customer> map = new HashMap<>();
		ArrayList<Customer> cands = new ArrayList<>();
		ArrayList<Customer> daddy = new ArrayList<>();
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < arr.length; i++) {
			int id = arr[i];
			boolean buyOrRefund = op[i];
			if (!buyOrRefund && !map.containsKey(id)) {
				ans.add(getCurAns(daddy));
				continue;
			}
			// 没有发生:用户购买数为0并且又退货了
			// 用户之前购买数是0,此时买货事件
			// 用户之前购买数>0, 此时买货
			// 用户之前购买数>0, 此时退货
			if (!map.containsKey(id)) {
				map.put(id, new Customer(id, 0, 0));
			}
			// 买、卖
			Customer c = map.get(id);
			if (buyOrRefund) {
				c.buy++;
			} else {
				c.buy--;
			}
			if (c.buy == 0) {
				map.remove(id);
			}
			// c
			// 下面做
			if (!cands.contains(c) && !daddy.contains(c)) {
				if (daddy.size() < k) {
					c.enterTime = i;
					daddy.add(c);
				} else {
					c.enterTime = i;
					cands.add(c);
				}
			}
			cleanZeroBuy(cands);
			cleanZeroBuy(daddy);
			cands.sort(new CandidateComparator());
			daddy.sort(new DaddyComparator());
			move(cands, daddy, k, i);
			ans.add(getCurAns(daddy));
		}
		return ans;
	}

	public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
		if (cands.isEmpty()) {
			return;
		}
		// 候选区不为空
		if (daddy.size() < k) {
			Customer c = cands.get(0);
			c.enterTime = time;
			daddy.add(c);
			cands.remove(0);
		} else { // 等奖区满了,候选区有东西
			if (cands.get(0).buy > daddy.get(0).buy) {
				Customer oldDaddy = daddy.get(0);
				daddy.remove(0);
				Customer newDaddy = cands.get(0);
				cands.remove(0);
				newDaddy.enterTime = time;
				oldDaddy.enterTime = time;
				daddy.add(newDaddy);
				cands.add(oldDaddy);
			}
		}
	}

	public static void cleanZeroBuy(ArrayList<Customer> arr) {
		List<Customer> noZero = new ArrayList<Customer>();
		for (Customer c : arr) {
			if (c.buy != 0) {
				noZero.add(c);
			}
		}
		arr.clear();
		for (Customer c : noZero) {
			arr.add(c);
		}
	}

	public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
		List<Integer> ans = new ArrayList<>();
		for (Customer c : daddy) {
			ans.add(c.id);
		}
		return ans;
	}

	// 为了测试
	public static class Data {
		public int[] arr;
		public boolean[] op;

		public Data(int[] a, boolean[] o) {
			arr = a;
			op = o;
		}
	}

	// 为了测试
	public static Data randomData(int maxValue, int maxLen) {
		int len = (int) (Math.random() * maxLen) + 1;
		int[] arr = new int[len];
		boolean[] op = new boolean[len];
		for (int i = 0; i < len; i++) {
			arr[i] = (int) (Math.random() * maxValue);
			op[i] = Math.random() < 0.5 ? true : false;
		}
		return new Data(arr, op);
	}

	// 为了测试
	public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
		if (ans1.size() != ans2.size()) {
			return false;
		}
		for (int i = 0; i < ans1.size(); i++) {
			List<Integer> cur1 = ans1.get(i);
			List<Integer> cur2 = ans2.get(i);
			if (cur1.size() != cur2.size()) {
				return false;
			}
			cur1.sort((a, b) -> a - b);
			cur2.sort((a, b) -> a - b);
			for (int j = 0; j < cur1.size(); j++) {
				if (!cur1.get(j).equals(cur2.get(j))) {
					return false;
				}
			}
		}
		return true;
	}

	public static void main(String[] args) {
		int maxValue = 10;
		int maxLen = 100;
		int maxK = 6;
		int testTimes = 100000;
		System.out.println("测试开始");
		for (int i = 0; i < testTimes; i++) {
			Data testData = randomData(maxValue, maxLen);
			int k = (int) (Math.random() * maxK) + 1;
			int[] arr = testData.arr;
			boolean[] op = testData.op;
			List<List<Integer>> ans1 = topK(arr, op, k);
			List<List<Integer>> ans2 = compare(arr, op, k);
			if (!sameAnswer(ans1, ans2)) {
				for (int j = 0; j < arr.length; j++) {
					System.out.println(arr[j] + " , " + op[j]);
				}
				System.out.println(k);
				System.out.println(ans1);
				System.out.println(ans2);
				System.out.println("出错了!");
				break;
			}
		}
		System.out.println("测试结束");
	}

}

3.3什么时候用加强堆

用到这个结构的题目特征:

需要用到堆结构来维持样本之间的大小关系,

又有样本数值改变的需求,还需要在结构里调整排列次序,

样本数值之间允许重复,也就是在结构里数值一样的样本不希望去重,希望都保留。

这是加强堆的使用特征。

完全可以把这个结构当作堆的coding练习,事实上这个结构也确实是练习意义大于实际意义的结构。

3.4加强堆-其他题

力扣508-出现次数最多的子树元素和

508. 出现次数最多的子树元素和

解法:

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// 加强堆
class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        Heap heap = new Heap();
        findFrequentTreeSum(root, heap);
        return getMaxNum(heap);
    }

    private int findFrequentTreeSum(TreeNode root, Heap heap) {
        if (root == null)
            return 0;
        int left = findFrequentTreeSum(root.left, heap);
        int right = findFrequentTreeSum(root.right, heap);
        int sum = left + right + root.val;
        heap.insert(sum);
        return sum;
    }

    private int[] getMaxNum(Heap heap) {
        if (heap.isEmpty()) {
            return new int[0];
        }
        int num = heap.peek().num;
        List<Integer> result = new LinkedList<>();
        while (!heap.isEmpty() && heap.peek().num == num) {
            result.add(heap.pop().sum);
        }
        int[] arr = new int[result.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }

    class Data {
        int sum;
        int num;

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Data data = (Data) o;
            return sum == data.sum && num == data.num;
        }

        @Override
        public int hashCode() {
            return Objects.hash(sum, num);
        }
    }

    class Heap {
        ArrayList<Data> heap;
        Map<Integer, Integer> indexMap;

        int heapSize = 0;

        public Heap() {
            heap = new ArrayList<>();
            indexMap = new HashMap<>();
        }

        public void insert(int sum) {
            if (indexMap.containsKey(sum)){
                heap.get(indexMap.get(sum)).num++;
                resign(indexMap.get(sum));
            } else {
                Data data = new Data();
                data.sum = sum;
                data.num++;
                heap.add(data);
                indexMap.put(data.sum, heapSize);
                heapInsert(heapSize++);
            }
        }

        public Data peek() {
            return heap.get(0);
        }


        public boolean isEmpty(){
            return heapSize == 0;
        }

        public Data pop() {
            Data data = heap.get(0);
            remove(data.sum);
            return data;
        }

        public void resign(int index) {
            heapInsert(index);
            heapIfy(index);
        }

        public void remove(int sum) {
            Integer index = indexMap.get(sum);
            Data last = heap.get(heapSize - 1);
            indexMap.remove(sum);
            heapSize--;
            if (last.sum != sum) {
                indexMap.put(last.sum, index);
                heap.set(index, last);
                resign(index);
            }
        }

        private void heapIfy(int index) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                int largest = left + 1 < heapSize && heap.get(left + 1).num > heap.get(left).num ? left + 1 : left;
                largest = heap.get(index).num > heap.get(largest).num ? index : largest;
                if (index == largest) {
                    break;
                }
                swap(index, largest);
                index = largest;
                left = index * 2 + 1;
            }
        }

        private void heapInsert(int index) {
            while (true) {
                int parent = (index - 1) / 2;
                if (!(heap.get(parent).num < heap.get(index).num)) break;
                swap(parent, index);
                index = parent;
            }
        }

        private void swap(int left, int right) {
            Data l = heap.get(left);
            Data r = heap.get(right);
            indexMap.put(l.sum, right);
            indexMap.put(r.sum, left);
            heap.set(left, r);
            heap.set(right, l);
        }
    }
}

4.力扣-295

295. 数据流的中位数

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
class MedianFinder {

    PriorityQueue<Integer> hMax;
    PriorityQueue<Integer> hMin;

    public MedianFinder() {
        hMax = new PriorityQueue<>((a, b)->b - a);
        hMin = new PriorityQueue<>((a, b)->a - b);
    }
    
    public void addNum(int num) {
        if (hMax.isEmpty()) {
            hMax.add(num);
        } else if (hMax.peek() >= num) {
            hMax.add(num);
        } else {
            hMin.add(num);
        }
        balance();
    }
    
    public double findMedian() {
        if (hMax.size() == hMin.size()) {
            return (double)(hMax.peek() + hMin.peek()) / 2;
        } else {
            return hMax.size() > hMin.size() ? hMax.peek() : hMin.peek();
        }
    }    

    public void balance() {
        if (hMax.size() == hMin.size() + 2) {
            hMin.add(hMax.poll());
        } else if (hMin.size() == hMax.size() + 2) {
            hMax.add(hMin.poll());
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */