|
为什么要手写加强堆？
因为系统提供的堆(PriorityQueue)没有反向索引表，无法快速找到元素和删除某个元素，如果要实现的话查找的代价是O(N)，删除元素的代价是O(N*logN)
直接上代码，看不懂的私信我
package dataStructure.heap;
import java.util.Comparator;
import java.util.HashMap;
/**
* 自写加强堆
* 可以实现低成本删除任意元素
* @param
*/
public class HeapGreater {
//反向索引表，用于记录某个元素在heap数组中的下标，主要用于快速删除元素
HashMap reverseIndex = new HashMap();
T[] heap;
int limit;
int heapSize;
//T类型的比较器
Comparator comp;
public HeapGreater(int limit, Comparator comp) {
heap = (T[])new Object[limit];
this.limit = limit;
heapSize = 0;
this.comp = comp;
}
//堆是否为空
public boolean isEmpty() {
return heapSize == 0;
}
//堆是否已满
public boolean isFull() {
return heapSize == limit;
}
//删除一个元素并重新调整为大根堆
public void remove(T t) {
//为空不可能删除
if(isEmpty()) {
throw new RuntimeException("heap is empty");
}
//没有这个元素无法删除
if(!reverseIndex.containsKey(t)) {
return;
}
//反向索引表获取元素在数组中的下标
int index = reverseIndex.get(t);
//交换要删除的元素和堆中最后一个元素
//heapSize--
swap(heap, index, --heapSize);
//元素要删除，反向索引表也应该删除
reverseIndex.remove(t);
//删除以后重新调整，最后一个元素已经换到了index位置，从index位置向下调整
heapify(index);
//从index往上调整，向上和向下只会发生一个
heapInsert(index);
}
//弹出堆顶元素并重新调整成大根堆
public T pop() {
if(isEmpty()) {
throw new RuntimeException("heap is empty");
}
//取到堆顶元素
T t = heap[0];
//把堆顶和堆中最后一个元素交换
swap(heap, 0, --heapSize);
//反向索引表删除要删除的元素
reverseIndex.remove(t);
//重新调整为大根堆
heapify(0);
return t;
}
/**
* 从index开始向下调整大根堆
* @param index
*/
public void heapify(int index) {
//取到当前节点的左孩子
int left = index * 2 + 1;
//左孩子是两个孩子里下标比较小的，如果它都不在堆里，就无需调整
while(left < heapSize) {
//找到两个孩子里比较大的那个
int largest = left + 1 >= heapSize?
left : comp.compare(heap[left], heap[left + 1]) >= 0? left : left + 1;
//largest取当前值和最大孩子里最大那个
largest = comp.compare(heap[largest],heap[index]) < 0? index : largest;
//如果最大值是自己直接返回
if(largest == index) return;
//如果不是则交换自己和最大孩子
swap(heap, largest, index);
//当前节点已调整到最大孩子位置，继续调整
index = largest;
left = 2 * index + 1;
}
}
//往堆里添加一个元素
public void push(T t) {
if(isFull()) {
throw new RuntimeException("heap is full");
}
heap[heapSize] = t;
//添加反向索引表记录
reverseIndex.put(t, heapSize);
heapInsert(heapSize ++);
}
//从index向上调整大根堆
public void heapInsert(int index) {
while(comp.compare(heap[index], heap[(index -1 )/2]) > 0) {
swap(heap, index, (index - 1)/2);
index = (index - 1) / 2;
}
}
//交换i和j位置的元素
private void swap(T[] heap, int i, int j) {
//自己跟自己不需要调整
if(i == j) return;
T temp = heap[i];
//反向索引表i位置元素防止在j位置
reverseIndex.put(temp,j);
heap[i] = heap[j];
//i位置放置原来j位置的元素（已经交换到heap[j]）
reverseIndex.put(heap[i], i);
heap[j] = temp;
}
public static void main(String[] args) {
HeapGreater heapGreater = new HeapGreater(5, (a,b) -> a - b);
heapGreater.push(2);
heapGreater.push(3);
heapGreater.push(5);
heapGreater.push(1);
heapGreater.push(4);
heapGreater.remove(4);
System.out.println(heapGreater.reverseIndex.size());
}
}
|