加強堆結構說明
加強堆結構說明
作者：Grey
原文地址：
關於堆和堆排序的說明
可以參考這篇博客：與堆和堆排序相關的問題
基礎的堆結構可以實現數據入堆和出堆以後（即: 調用堆的 pop 和 push 方法），使用O(logN)的時間複雜度可以將堆調整好，如果使用的是 Java 語言，可以用 java.util 包中的 PriorityQueue 實現堆的所有操作。
但是，在實際場景中，有一種情況是：在已知的一個堆中，堆中任意一個元素變換後，也要以O(logN)的時間複雜度把堆結構調整正確。這是 Java 語言自帶的堆結構(PriorityQueue)無法做到的，這就引入了「加強堆」的概念。「加強堆」提供如下方法
public void resign(T obj) {
}
這個方法表示，對於堆中任意的一個元素 obj，如果調整了其對應的數值，整個堆結構還能在時間複雜度O(logN)下調整好。
普通堆結構之所以無法做到，是因為普通的堆結構沒有記錄任意一個數據所在的位置信息，所以無法從對應的位置進行堆結構調整。所以，「加強堆」結構引入了一個 HashMap
HashMap<T, Integer> indexMap; // 元素在堆中的位置
有了這個HashMap, 就可以很方便得到某個數據項在堆中的位置是什麼，在堆的pop和push方法中，要把HashMap的邏輯加入
public void push(T obj) {
heap.add(obj);
// obj 這個數據在堆中是什麼位置
indexMap.put(obj, heapSize);
heapInsert(heapSize++);
}
public T pop() {
T ans = heap.get(0);
swap(0, heapSize - 1);
// 要把對應的obj在堆中直接刪除
indexMap.remove(ans);
heap.remove(--heapSize);
heapify(0);
return ans;
}
更重要的是，在堆的 heapify 和 heapInsert 操作中，涉及到的堆中兩個元素的交換，也要把堆中元素的位置進行交換。
// 不要忘記把堆中元素的位置也要做交換！！！！
private void swap(int i, int j) {
T o1 = heap.get(i);
T o2 = heap.get(j);
heap.set(i, o2);
heap.set(j, o1);
indexMap.put(o2, i);
indexMap.put(o1, j);
}
以上是鋪墊，到了最核心的resign方法，其邏輯如下
public void resign(T obj) {
heapInsert(indexMap.get(obj));
heapify(indexMap.get(obj));
}
整個過程也非常好理解，就是找到變化的那個數據項的位置，然後執行heapify和heapInsert，由於變換過程無非是變大或者變小，所以找到變換的位置，heapify和heapInsert操作只會執行一個操作！另外一個操作進去以後會直接跳出。
加強堆的完整代碼如下（支持泛型）:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
public class Code_CustomHeap {
// 自己手寫堆
public static class HeapGreater<T> {
private ArrayList<T> heap;
private HashMap<T, Integer> indexMap; // 元素在堆中的位置
private int heapSize; // 和heap配合使用
private Comparator<? super T> comp;
public HeapGreater(Comparator<T> c) {
heap = new ArrayList<>();
indexMap = new HashMap<>();
comp = c;
}
public boolean isEmpty() {
return heapSize == 0;
}
public int size() {
return heapSize;
}
public boolean contains(T obj) {
return indexMap.containsKey(obj);
}
public T peek() {
return heap.get(0);
}
public void push(T obj) {
heap.add(obj);
indexMap.put(obj, heapSize);
heapInsert(heapSize++);
}
public T pop() {
T ans = heap.get(0);
swap(0, heapSize - 1);
indexMap.remove(ans);
heap.remove(--heapSize);
heapify(0);
return ans;
}
public void remove(T obj) {
T replace = heap.get(heapSize - 1);
int index = indexMap.get(obj);
indexMap.remove(obj);
heap.remove(--heapSize);
if (obj != replace) { // obj == replace表示刪掉的是最後一個位置的數據，此時不需要進行resign操作
heap.set(index, replace);
indexMap.put(replace, index);
resign(replace);
}
}
public void resign(T obj) {
heapInsert(indexMap.get(obj));
heapify(indexMap.get(obj));
}
// 請返回堆上的所有元素
public List<T> getAllElements() {
List<T> ans = new ArrayList<>();
for (T c : heap) {
ans.add(c);
}
return ans;
}
private void heapInsert(int index) {
while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private void heapify(int index) {
int left = index * 2 + 1;
while (left < heapSize) {
int best =
left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0
? (left + 1)
: left;
best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
if (best == index) {
break;
}
swap(best, index);
index = best;
left = index * 2 + 1;
}
}
private void swap(int i, int j) {
T o1 = heap.get(i);
T o2 = heap.get(j);
heap.set(i, o2);
heap.set(j, o1);
indexMap.put(o2, i);
indexMap.put(o1, j);
}
}
}
使用加強堆來解決的問題示例，見使用加強堆解決 topK 問題
