左神算法：加强堆的实现（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);} }

总结

以上是生活随笔为你收集整理的左神算法：加强堆的实现（Java）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。