增强堆：任意元素删除与更新
通过反向索引表扩展堆的能力，并用堆解决最大线段重合问题。
本文将深入探讨两个主题：首先，我们将剖析一个在传统堆基础上进行功能扩展的“增强堆”，它如何通过引入辅助结构实现对任意元素的高效操作；其次，我们将应用数据结构的知识，解决一个经典的“最大线段重合”问题。本篇基于上次的堆的基础进行书写，不再赘述已经讲过的堆的基本方法。
1. 增强堆
标准的堆（如Java中的 PriorityQueue）在提供快速访问顶部元素（最大或最小）方面非常高效，但它在某些操作上存在局限性，例如：无法高效地删除或更新堆中任意一个非顶部元素。为了克服这些限制，我们可以通过结合哈希表（HashMap）来构建一个功能更强大的“增强堆”。
1.1. 核心思路：引入反向索引表
增强堆的关键在于引入一个“反向索引表”（indexMap），它是一个哈希表，用于存储堆中每个元素当前在数组（ArrayList）中的具体位置（索引）。
- 传统堆的困境：在一个标准的堆中，如果要调整某个特定元素，我们首先需要遍历整个数组才能找到它，这个过程的时间复杂度是 O(N)。
- 增强堆的突破：有了
indexMap，我们可以用 O(1)的时间复杂度定位到任何元素在堆中的位置。这使得后续的调整（上浮或下沉）操作能够精准、高效地进行，整体操作的时间复杂度优化到 O(log N)。
1.2. 基础结构与核心操作
增强堆的数据结构主要由三部分组成：
ArrayList<T> heap：堆的底层存储，使用动态数组。HashMap<T, Integer> indexMap：反向索引表，记录元素到索引的映射。Comparator<? super T> comp：比较器，用于定义堆的排序规则（大根堆或小根堆）。
1.2.1. 交换操作（swap）
交换是堆调整的基础。在增强堆中，swap 操作不仅要交换数组中两个元素的位置，还必须同步更新它们在 indexMap 中的索引记录。这是确保索引表始终正确的关键。
java
public void swap(ArrayList<T> heap, int a, int b){
T temp = heap.get(a);
heap.set(a, heap.get(b));
heap.set(b, temp);
// 索引表索引同步更新
indexMap.put(heap.get(b), b);
indexMap.put(heap.get(a), a);
}1.3. 增强功能的实现
基于正确的索引映射，我们可以轻松实现对堆中任意元素的删除和调整。
1.3.1. 任意元素的删除（remove）
删除堆中任意一个元素的标准流程是：
- 通过
indexMap找到目标元素obj的索引idx。 - 将堆的最后一个元素
tailNode取出。 - 从
indexMap和heap中移除obj和最后一个元素。 - 如果被删除的
obj恰好不是最后一个元素，则将tailNode放置在idx位置，并更新其在indexMap中的索引。 - 最后，对
tailNode执行一次调整（resign），以恢复堆的有序性。
java
public void remove(T obj) {
T tailNode = heap.get(heapSize - 1);
int idx = indexMap.get(obj);
indexMap.remove(obj);
heap.remove(--heapSize);
if (tailNode != obj) {
heap.set(idx, tailNode);
indexMap.put(tailNode, idx);
resign(tailNode);
}
}1.3.2. 元素的调整（resign）
当堆中某个元素的值发生变化后，其在堆中的位置可能不再满足堆的性质。resign 方法就是为了解决这个问题。它通过对指定元素同时尝试执行“上浮”（heapInsert）和“下沉”（heapify）操作，来将其调整到正确的位置。由于一个元素要么需要上浮，要么需要下沉，这两个操作中只有一个会实际执行，另一个会因不满足循环条件而立即终止。
java
public void resign(T obj) {
heapInsert(heap, indexMap.get(obj));
heapify(heap, indexMap.get(obj));
}1.4. 完整代码实现
以下是 HeapGreater 的完整实现代码，它封装了上述所有逻辑，提供了一个功能完备且高效的增强堆。
java
package L7;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
public class HeapGreater<T> {
private ArrayList<T> heap;
private Integer heapSize;
private HashMap<T, Integer> indexMap;
private Comparator<? super T> comp;
public HeapGreater(Comparator<? super T> comp) {
this.heap = new ArrayList<>();
this.heapSize = 0;
this.indexMap = new HashMap<>();
this.comp = comp;
}
public int size() {
return heapSize;
}
public boolean isEmpty(){
return heapSize == 0;
}
public T peek() {
return heap.getFirst();
}
public boolean contains(T obj) {
return indexMap.containsKey(obj);
}
public void push(T obj){
heap.add(obj);
indexMap.put(obj, heapSize);
heapInsert(heap, heapSize++);
}
public void heapInsert(ArrayList<T> heap, int idx){
while (comp.compare(heap.get(idx), heap.get((idx - 1) / 2)) < 0) {
swap(heap, idx, (idx - 1) / 2);
idx = (idx - 1) / 2;
}
}
public T pop(){
if (isEmpty()) {
throw new RuntimeException("堆目前为空！无法弹出");
}
T rst = heap.getFirst();
swap(heap, 0, heapSize - 1);
indexMap.remove(heap.get(heapSize - 1));
heap.remove(--heapSize);
heapify(heap, 0);
return rst;
}
private void heapify(ArrayList<T> heap, int idx) {
int left = idx * 2 + 1;
while (left < heapSize) {
int right = left + 1;
int childMin = right < heapSize && comp.compare(heap.get(right), heap.get(left)) < 0 ? right : left;
int finalMin = comp.compare(heap.get(childMin), heap.get(idx)) < 0 ? childMin : idx;
if (finalMin == idx) {
break;
}
swap(heap, idx, finalMin);
idx = finalMin;
left = idx * 2 + 1;
}
}
public void swap(ArrayList<T> heap, int a, int b){
T temp = heap.get(a);
heap.set(a, heap.get(b));
heap.set(b, temp);
indexMap.put(heap.get(b), b);
indexMap.put(heap.get(a), a);
}
public void resign(T obj) {
heapInsert(heap, indexMap.get(obj));
heapify(heap, indexMap.get(obj));
}
public void remove(T obj) {
T tailNode = heap.get(heapSize - 1);
int idx = indexMap.get(obj);
indexMap.remove(obj);
heap.remove(--heapSize);
if (tailNode != obj) {
heap.set(idx, tailNode);
indexMap.put(tailNode, idx);
resign(tailNode);
}
}
public List<T> getAllElements() {
List<T> ans = new ArrayList<>();
for (T c : heap) {
ans.add(c);
}
return ans;
}
}2. 算法题解：最大线段重合问题
掌握了高效的数据结构后，我们来看一个能够巧妙利用堆来解决的经典问题。
2.1. 问题描述
给定一个包含多个线段的数组，每个线段由 [start, end] 两个整数表示（闭区间）。我们需要计算在所有线段中，重合区域最多包含了多少条线段。规定线段重合区域的长度必须大于等于1。
2.2. 核心思路：排序 + 最小堆
这个问题的最优解法是“扫描线”思想的体现，可以借助最小堆来实现。
- 排序：首先，将所有的线段按照
start端点从小到大进行排序。这确保我们总是按时间顺序处理线段的开始事件。 - 最小堆：我们使用一个最小堆（
PriorityQueue）来存放当前“活跃”线段的end端点。堆顶始终是所有活跃线段中最早结束的那个。 - 遍历与处理：我们依次遍历排序后的线段数组。当处理第
i条线段lines[i]时：- 移除已结束的线段：检查堆顶。如果堆顶的
end值小于或等于当前线段的start值（pq.peek() <= lines[i].start），说明堆顶代表的线段在当前线段开始之前就已经结束了，不构成重合。因此，将其从堆中弹出。重复此过程，直到堆为空或堆顶的end值大于lines[i].start。 - 加入当前线段：将当前线段的
end值（lines[i].end）加入最小堆。 - 更新最大值：此时，堆的大小
pq.size()就代表了在lines[i].start这个时间点上，总共有多少条线段是重合的。我们用一个变量max来记录这个过程中的最大值。
- 移除已结束的线段：检查堆顶。如果堆顶的
遍历完所有线段后，max 中存储的就是最终的答案。
图解思路
plaintext
线段按 start 排序: (1,5), (2,4), (3,6), (7,8)
i=0, line=(1,5):
- 堆中清理: (堆为空)
- (1,5) 的 end=5 入堆. 堆: [5]
- 当前重合数: 1. max=1
i=1, line=(2,4):
- 堆中清理: 堆顶 5 > start 2. 无需清理.
- (2,4) 的 end=4 入堆. 堆: [4, 5]
- 当前重合数: 2. max=2
i=2, line=(3,6):
- 堆中清理: 堆顶 4 > start 3. 无需清理.
- (3,6) 的 end=6 入堆. 堆: [4, 5, 6]
- 当前重合数: 3. max=3
i=3, line=(7,8):
- 堆中清理:
- 堆顶 4 <= start 7. 弹出 4. 堆: [5, 6]
- 堆顶 5 <= start 7. 弹出 5. 堆: [6]
- 堆顶 6 <= start 7. 弹出 6. 堆: []
- (7,8) 的 end=8 入堆. 堆: [8]
- 当前重合数: 1. max 维持 3
遍历结束, 最终答案: 32.3. 代码实现
下面是该思路的Java代码实现。代码中定义了 Line 类和用于排序的比较器 LineComp。
java
package L7;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;
public class MaxCover {
public static class Line {
public int start;
public int end;
public Line() {
}
public Line(int start, int end) {
this.start = start;
this.end = end;
}
}
public static class LineComp implements Comparator<Line> {
@Override
public int compare(Line o1, Line o2) {
return o1.start - o2.start;
}
}
public static int getMaxCover(Line[] lines) {
if (lines == null || lines.length < 2) {
return 0;
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
int[] count = new int[lines.length];
Arrays.sort(lines, new LineComp());
int max = -1;
for (int i = 0; i < lines.length; i++) {
pq.add(lines[i].end);
while (!pq.isEmpty() && pq.peek() <= lines[i].start) {
pq.poll();
}
count[i] = pq.size();
max = Math.max(max, count[i]);
}
return max;
}2.4. 算法验证：对数器
为了确保我们算法的正确性，代码中还提供了一个“对数器”——即一个暴力解法（getMaxCoverBruteForce）和一套随机测试框架。
- 暴力解法：找到所有线段坐标的最大和最小值，然后遍历这个范围内的每一个点（例如
min + 0.5,min + 1.5, ...），统计覆盖每个点的线段数，并取最大值。 - 随机测试：通过大量生成随机线段数据，分别用我们的解法和暴力解法进行计算，对比结果是否一致。这是一种非常有效的验证算法正确性的工程方法。
java
public static int getMaxCoverBruteForce(Line[] lines) {
if (lines == null || lines.length < 2) {
return 0;
}
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (Line line : lines) {
if (line.start < min) min = line.start;
if (line.end > max) max = line.end;
}
if (min == Integer.MAX_VALUE) {
return 0;
}
int ans = 0;
for (double p = min + 0.5; p < max; p += 1.0) {
int cur = 0;
for (Line line : lines) {
if (line.start <= p && line.end >= p) {
cur++;
}
}
ans = Math.max(ans, cur);
}
return ans;
}
public static Line[] generateRandomLines(int maxN, int minV, int maxV) {
Random r = new Random();
int n = r.nextInt(maxN + 1);
Line[] arr = new Line[n];
for (int i = 0; i < n; i++) {
int a = r.nextInt(maxV - minV + 1) + minV;
int b = r.nextInt(maxV - minV + 1) + minV;
if (a == b) {
if (b < maxV) {
b++;
} else {
a--;
}
}
int start = Math.min(a, b);
int end = Math.max(a, b);
arr[i] = new Line(start, end);
}
return arr;
}
public static Line[] copyLines(Line[] src) {
if (src == null) return null;
Line[] copy = new Line[src.length];
for (int i = 0; i < src.length; i++) {
copy[i] = new Line(src[i].start, src[i].end);
}
return copy;
}
public static void printLines(Line[] arr) {
if (arr == null) {
System.out.println("null");
return;
}
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
System.out.print("(" + arr[i].start + "," + arr[i].end + ")");
if (i != arr.length - 1) System.out.print(", ");
}
System.out.println("]");
}
public static void main(String[] args) {
int testTime = 5000;
int maxN = 8;
int minV = 0;
int maxV = 20;
System.out.println("开始随机测试，共 " + testTime + " 轮 ...");
for (int i = 1; i <= testTime; i++) {
Line[] data1 = generateRandomLines(maxN, minV, maxV);
Line[] data2 = copyLines(data1);
int ans1 = getMaxCover(data1);
int ans2 = getMaxCoverBruteForce(data2);
if (ans1 != ans2) {
System.out.println("第 " + i + " 轮出现不一致！");
System.out.println("题解结果: " + ans1 + ", 暴力结果: " + ans2);
System.out.println("线段数组：");
printLines(data2);
return;
}
}
System.out.println("测试完成，所有结果均一致！");
}
}3. 总结
本文通过两个案例展示了算法学习的两个重要方面。第一，通过对基础数据结构（堆）的改造，我们创造出功能更强大的工具，能够解决更复杂的问题；第二，通过对具体问题（线段覆盖）的分析，我们学习了如何选择和组合合适的数据结构（排序数组+最小堆）来设计出高效且优雅的解决方案。希望这次的分享能对你有所启发。