Реализация приоритетной очереди с updatePriority O (log n) - PullRequest
Новая
       37

Реализация приоритетной очереди с updatePriority O (log n)

0 голосов
/ 17 мая 2018

Мне нужно реализовать функцию со сложностью 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);
      } 
    }
  }
 }

PriorityQueue: 

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

Эта очередь приоритетов позже должна использоваться для реализации алгоритма Прима,Итак, что я могу сделать, чтобы получить O (1) сложность доступа?

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

В вашем методе add есть ошибка. Эта строка: 

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

|| должно быть &&

0 голосов
/ 17 мая 2018

Я могу думать о двух подходах:

  1. Вы можете добавить Map<V, Integer>, который отображает значения в индексы.Это означает некоторую дополнительную бухгалтерию, но это не слишком плохо, потому что вам нужно обновить его точно, когда вы добавляете или перемещаете элемент в своем основном массиве, так что вы можете легко поместить это в один setElement методчто вы всегда используете при манипулировании массивом.(Вы даже можете переместить сам массив в вспомогательный класс, который его обрабатывает.)
  2. При обновлении приоритета не обязательно удалять исходный элемент;в зависимости от остальной части вашего алгоритма, может быть просто добавить новый и пометить старый как «удаленный».(Удаленные элементы могут быть удалены из массива либо периодически (постоянное время амортизации), либо при обнаружении.) Это можно сделать, добавив отображение Map<V, Element<K, V>> из значения в текущий элемент.Вы можете либо добавить явный «удаленный» флаг в свой класс Element, либо просто посчитать элемент как удаленный, если его значение больше не отображается на него в вашем Map<V, Element<K, V>>.
...