具有 updatePriority O(log n) 的优先级队列实现

Question

我必须实现一个复杂度为 O(log n) 的函数，它更新优先级队列中元素的优先级。这意味着给定一个元素，访问它的优先级应该是 O(1)。我真的不明白如何做到这一点，如果所有元素都存储在堆中，并且它们的位置不断变化，这让我在堆中搜索元素的时间为 O(n)。

堆：

public class Heap<K, V> {
  private int size;
  private Element<K, V> heap[];
  private Comparator<? super K>  comparator;

  public Heap(Comparator<? super K>  comparator) {
  //
  }

  //
  public void add(K priority, V value) {
    int i;

    size++;
    if(size > heap.size()) resize();

    i = size;
    heap[i] = new Element(priority, value);

    while(i > 0 || comparator.compare(heap[parent(i)].priority, heap[i].priority) < 0) {
      swap(i, parent(i));
    }
  }

  // O(log n)
  public void updatePriority(int i, K priority) {
    K oldPriority = heap[i].priority;
    heap[i] = new Element(priority, heap[i].value);

    if(comparator.compare(oldPriority, heap[i].priority) > 0) {
      heapify(i);
    } else {
      while(i > 0 && comparator.compare(heap[parent(i)].priority, heap[i].priority)) < 0) {
        swap(i, parent(i));
        i = parent(i);
      } 
    }
  }
 }

优先队列：

public class PriorityQueue<K, V> {

  private Heap<Element<K, V>> heap;
  private Comparator<? super K>  comparator;

  public PriorityQueue(Comparator<? super K>  comparator) {
    heap = new Heap<K, V>(comparator);
  }

  //

  // Should be O(log n)
  public void updatePriority(K priority, V elem) {
    // get index of elem in O(1)
    heap.updatePriority(indexOfElem, priority);
  }
}

元素：

public class Element<K, V> {
  public K priority;
  public V value;

  public Element(K priority, V value) {
    this.priority = priority;
    this.value = value;
  }
}

这个优先级队列后面应该是用来实现Prim的算法的。那么我该怎么做才能获得 O(1) 的访问复杂度？

Answer 1

我可以想到两种方法：

您可以添加一个从值映射到索引的 Map<V, Integer>。这意味着一些额外的簿记工作，但还不错太，因为您需要在主数组中添加或移动元素时准确地更新它，因此您可以轻松地将它放在一个setElement 操作数组时经常使用的方法。（您甚至可以将数组本身移动到处理它的助手 class 中。）
更新优先级时，不一定需要移除原有元素；根据您算法的其余部分，简单地添加新的并将旧的标记为 "deleted" 可能没问题。（删除的元素可以定期（摊销常数时间）或在检测到时从数组中清除。）您可以通过添加从值到当前元素的 Map<V, Element<K, V>> 映射来实现。您可以向 Element class 添加明确的 "deleted" 标志，或者如果某个元素的值不再映射到您的 Map<V, Element<K, V>> 中，则将其计为已删除元素。 =22=]

Answer 2

您的 add 方法存在错误。这一行：

while(i > 0 || comparator.compare(heap[parent(i)].priority, heap[i].priority) < 0) {

||应该是&&

具有 updatePriority O(log n) 的优先级队列实现

Priority queue implementation with updatePriority O(log n)

java

algorithm

heap

priority-queue

data-structures