為什么要有加強堆？

Java中的PriorityQueue（優先級隊列）就是系統提供的堆實現，那么為什么還要手動去實現？

假如現在你手里有一個堆，里面存著一些元素，用戶此時說要改變元素的排序指標且要求高效，怎么辦？用系統實現的堆，你是不是只能把堆中的元素拿出來再重新去調整。

此時你的用戶又想刪除堆中的某一個元素，你要怎么刪除指定元素又能保證堆結構呢？系統提供的堆是不是無能為力，或者說系統提供的堆不能高效的滿足你的需求，你只能去手動改寫。

這里我們想一想：系統的堆為什么不能滿足我們的需求，根本原因在于：元素進堆之后，我們不能確定元素在堆的位置，如果我們能知道堆中元素的位置，不管調整還是刪除元素，是不是只需要在它的當前位置進行heapInsert或者heapify操作就可以了。

這就是加強堆的作用，給堆中的元素增加一張反向索引表，記錄入堆元素的位置，用來滿足我們的需求。具體代碼如下：

代碼

騰訊課堂

package class04_07;import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List;/** T一定要是非基礎類型，有基礎類型需求包一層*/ public class HeapGreater<T> {private ArrayList<T> heap;private HashMap<T, Integer> indexMap;private int heapSize;private Comparator<? super T> comp;public HeapGreater(Comparator<T> c) {heap = new ArrayList<>();indexMap = new HashMap<>();heapSize = 0;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) {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);} }

總結

以上是生活随笔為你收集整理的左神算法：加强堆的实现（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。