Priority queue implementation with updatePriority O(log n)

Question

I have to implement a function with complexity O(log n), that updates priority of an element in the priority queue. That means that given an element, access to its priority should be O(1). I don't really understand how this can be done, if all elements are stored in a heap, and their position is constantly changing, which gives me O(n) search of the element in the heap.

Heap :

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

Element:

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

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

This priority queue later should be used to implement Prim's algorithm. So what can I do to get O(1) access complexity?

you keep a mapping of elements to their indices, and every time you do a swap, you also swap in that mapping — k_ssb
Possible duplicate of Prim's Algorithm: How to get index of key on which DECREASE_KEY operation is to be performed? — Matt Timmermans

ruakh ruakh · Accepted Answer · 2018-05-17T17:25:17

I can think of two approaches:

You can add a Map<V, Integer> that maps from values to indices. This means some extra bookkeeping, but it's not too bad, because you need to update it exactly when you add or move an element in your main array, so you can easily put that in a single setElement method that you always use when manipulating the array. (You could even move the array itself into a helper class that handles that.)
When updating priority, you don't necessarily need to remove the original element; depending on the rest of your algorithm, it may be fine to simply add the new one and mark the old one as "deleted". (Deleted elements can be cleared from the array either periodically (amortized-constant time) or when detected.) You can do this by adding a Map<V, Element<K, V>> mapping from the value to the current element. You can either add an explicit "deleted" flag to your Element class, or just count an element as deleted if its value is no longer mapped to it in your Map<V, Element<K, V>>.

Priority queue implementation with updatePriority O(log n)

2 Answers