左神算法：加强堆的实现（Java）

本文主要是介绍左神算法：加强堆的实现（Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

为什么要有加强堆？

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);}
}