时间戳

首页 > 解决方案 > updatePriority O(log n) 的优先级队列实现

java - updatePriority O(log n) 的优先级队列实现

问题描述

我必须实现一个复杂度为 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) 访问复杂度呢？

标签： javaalgorithmdata-structuresheappriority-queue

解决方案

我可以想到两种方法：

  1. 您可以添加Map<V, Integer>从值映射到索引的 a。这意味着一些额外的簿记，但这还不错，因为当您在主数组中添加或移动元素时，您需要准确地更新它，因此您可以轻松地将其放入setElement您在操作数组时始终使用的单一方法中。（您甚至可以将数组本身移动到处理它的辅助类中。）
  2. 更新优先级时，不一定需要移除原来的元素；根据您算法的其余部分，只需添加新的并将旧的标记为“已删除”就可以了。（已删除的元素可以定期（摊销的常数时间）或在检测到时从数组中清除。）您可以通过添加Map<V, Element<K, V>>从值到当前元素的映射来做到这一点。您可以向您的Element类添加显式“已删除”标志，或者如果元素的值不再映射到您的Map<V, Element<K, V>>.

推荐阅读