PriorityQueue/Heap Update

Question

Does Java have an easy way to reevaluate a heap once the priority of an object in a PriorityQueue has changed? I can't find any sign of it in Javadoc, but there has to be a way to do it somehow, right? I'm currently removing the object then re-adding it but that's obviously slower than running update on the heap.

Answer 1

You might need to implement such a heap yourself. You need to have some handle to the position of the item in the heap, and some methods to push the item up or down when its priority has changed.

Some years ago I wrote such a heap as part of a school work. Pushing an item up or down is an O(log N) operation. I release the following code as public domain, so you may use it in any way you please. (You might want to improve this class so that instead of the abstract isGreaterOrEqual method the sort order would rely on Java's Comparator and Comparable interfaces, and also would make the class use generics.)

import java.util.*;

public abstract class Heap {

    private List heap;

    public Heap() {
        heap = new ArrayList();
    }

    public void push(Object obj) {
        heap.add(obj);
        pushUp(heap.size()-1);
    }

    public Object pop() {
        if (heap.size() > 0) {
            swap(0, heap.size()-1);
            Object result = heap.remove(heap.size()-1);
            pushDown(0);
            return result;
        } else {
            return null;
        }
    }

    public Object getFirst() {
        return heap.get(0);
    }

    public Object get(int index) {
        return heap.get(index);
    }

    public int size() {
        return heap.size();
    }

    protected abstract boolean isGreaterOrEqual(int first, int last);

    protected int parent(int i) {
        return (i - 1) / 2;
    }

    protected int left(int i) {
        return 2 * i + 1;
    }

    protected int right(int i) {
        return 2 * i + 2;
    }

    protected void swap(int i, int j) {
        Object tmp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, tmp);
    }

    public void pushDown(int i) {
        int left = left(i);
        int right = right(i);
        int largest = i;

        if (left < heap.size() && !isGreaterOrEqual(largest, left)) {
            largest = left;
        }
        if (right < heap.size() && !isGreaterOrEqual(largest, right)) {
            largest = right;
        }

        if (largest != i) {
            swap(largest, i);
            pushDown(largest);
        }
    }

    public void pushUp(int i) {
        while (i > 0 && !isGreaterOrEqual(parent(i), i)) {
            swap(parent(i), i);
            i = parent(i);
        }
    }

    public String toString() {
        StringBuffer s = new StringBuffer("Heap:\n");
        int rowStart = 0;
        int rowSize = 1;
        for (int i = 0; i < heap.size(); i++) {
            if (i == rowStart+rowSize) {
                s.append('\n');
                rowStart = i;
                rowSize *= 2;
            }
            s.append(get(i));
            s.append(" ");
        }
        return s.toString();
    }

    public static void main(String[] args){
        Heap h = new Heap() {
            protected boolean isGreaterOrEqual(int first, int last) {
                return ((Integer)get(first)).intValue() >= ((Integer)get(last)).intValue();
            }
        };

        for (int i = 0; i < 100; i++) {
            h.push(new Integer((int)(100 * Math.random())));
        }

        System.out.println(h+"\n");

        while (h.size() > 0) {
            System.out.println(h.pop());
        }
    }
}

Answer 2

PriorityQueue has the heapify method which re-sorts the entire heap, the fixUp method, which promotes an element of higher priority up the heap, and the fixDown method, which pushes an element of lower priority down the heap. Unfortunately, all of these methods are private, so you can't use them.

I'd consider using the Observer pattern so that a contained element can tell the Queue that its priority has changed, and the Queue can then do something like fixUp or fixDown depending on if the priority increased or decreased respectively.

Answer 3

That's right. PriorityQueue of Java does not offer a method to update priority and it seems that deletion is taking linear time since it does not store objects as keys, as Map does. It in fact accepts same object multiple times.

I also wanted to make PQ offering update operation. Here is the sample code using generics. Any class that is Comparable can be used with it.

class PriorityQueue<E extends Comparable<E>> {
    List<E> heap = new ArrayList<E>();
    Map<E, Integer> map = new HashMap<E, Integer>();

    void insert(E e) {
        heap.add(e);
        map.put(e, heap.size() - 1);
        bubbleUp(heap.size() - 1);
    }

    E deleteMax() {
        if(heap.size() == 0)
            return null;
        E result = heap.remove(0);
        map.remove(result);
        heapify(0);
        return result;
    }

    E getMin() {
        if(heap.size() == 0)
            return null;
        return heap.get(0);
    }

    void update(E oldObject, E newObject) {
        int index = map.get(oldObject);
        heap.set(index, newObject);
        bubbleUp(index);
    }

    private void bubbleUp(int cur) {
        while(cur > 0 && heap.get(parent(cur)).compareTo(heap.get(cur)) < 0) {
            swap(cur, parent(cur));
            cur = parent(cur);
        }
    }

    private void swap(int i, int j) {
        map.put(heap.get(i), map.get(heap.get(j)));
        map.put(heap.get(j), map.get(heap.get(i)));
        E temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    private void heapify(int index) {
        if(left(index) >= heap.size())
            return;
        int bigIndex = index;
        if(heap.get(bigIndex).compareTo(heap.get(left(index))) < 0)
            bigIndex = left(index);
        if(right(index) < heap.size() && heap.get(bigIndex).compareTo(heap.get(right(index))) < 0)
            bigIndex = right(index);
        if(bigIndex != index) {
            swap(bigIndex, index);
            heapify(bigIndex);
        }
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

    private int left(int i) {
        return 2*i + 1;
    }

    private int right(int i) {
        return 2*i + 2;
    }
}

Here while updating, I am only increasing the priority (for my implementation) and it is using MaxHeap, so I am doing bubbleUp. One may need to heapify based on requirement.

Answer 4

The standard interfaces don't provide an update capability. You have use a custom type that implements this.

And you're right; although the big-O complexity of algorithms that use a heap doesn't change when you remove and replace the top of the heap, their actual run time can nearly double. I'd like to see better built-in support for a peek() and update() style of heap usage.

Answer 5

Unfortunately, JDK's Priority Queue doesn't provide updates. Robert Sedgewick and Kevin Wayne are well known for their algorithms courses in Princeton, and they also wrote Algorithms.

Inside this excellent book, they provide their own implementations for data structures, including updateable priority queues, such as IndexMinPQ.java

Licensed under GPLv3.

Answer 6

Depending on the implementation of the data structure, there may not be a faster way. Most PQ/heap algorithms do not provide an update function. The Java implementation may not be any different. Notice that though a remove/insert makes the code slower, it is unlikely to result in code with a different runtime complexity.

Edit: have a look at this thread: A priority queue which allows efficient priority update?

Answer 7

You need to implement it yourself. But you don't have to get fancy. The actual massive timesuck of removing the heap item in Java's implementation of remove(Object) is actually indexOf() since it has to iterate the entire list to find the index of the particular object. If you implement your own datastructure you can tell each object the position in the array and even if your implementation isn't anything fancy it'll outperform Java's since each object would know where its located in the array.

Storing that information you can do just the classic remove and add the new item and you'll beat Java by a lot.

The update routine just calls heapify on the particular index. It saves a heapify call, and some constant operations. The bulk of the optimization here is that Java's actual PriorityQueue can't store the index. So remove(Object) is actually a pretty expensive operation within that datastructure. As you're going to have to locate that Object in the list. This particular class reduces the time taken by PriorityQueue to nearly nothing. Though it requires that you implement Heap.Indexed on the items you put in the heap.

import java.util.Arrays;

public class Heap<T extends Heap.Indexed<T>> {

    private Indexed[] heap;
    private int length = 0;

    public Heap() {
        heap = new Indexed[12];
    }

    private void ensureCapacity() {
        if (length > heap.length) {
            heap = Arrays.copyOf(heap, length * 2);
        }
    }

    public void add(T obj) {
        int index = length++;
        ensureCapacity();
        obj.setIndex(index);
        heap[index] = obj;
        heapify(index);
    }

    public T removeAt(int index) {
        T result = get(index);
        length -= 1;
        if ((length > 0) && (index != length)) {
            swap(index, length);
            heapify(index);
        }
        result.setIndex(-1);
        heap[length] = null;
        return result;
    }

    public T remove(T obj) {
        int index = obj.getIndex();
        if (index == -1) {
            return null;
        }
        return removeAt(index);
    }

    public void update(T obj) {
        int index = obj.getIndex();
        obj.setIndex(-1);
        if (index == -1) {
            return;
        }
        heapify(index);
    }

    public T poll() {
        if (length == 0) {
            return null;
        }
        return removeAt(0);
    }

    public T peek() {
        return get(0);
    }

    public T get(int index) {
        return (T) heap[index];
    }

    public int size() {
        return length;
    }

    protected boolean compare(int first, int last) {
        return get(first).compareTo(get(last)) > -1;
    }

    protected void swap(int i, int j) {
        T tmp = (T) heap[i];
        heap[i] = (T) heap[j];
        heap[j] = tmp;
        heap[i].setIndex(i);
        heap[j].setIndex(j);
    }

    public void heapify(int index) {
        int parent = (index - 1) / 2;
        if (index > 0 && !compare(parent, index)) {
            swap(parent, index);
            heapify(parent);
            return;
        }
        int left = (index << 1) + 1;
        int right = left + 1;
        int largest = index;

        if (left < length && !compare(largest, left)) {
            largest = left;
        }
        if (right < length && !compare(largest, right)) {
            largest = right;
        }

        if (largest != index) {
            swap(largest, index);
            heapify(largest);
        }
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public void clear() {
        this.length = 0;
        Arrays.fill(heap, null);
    }

    public interface Indexed<I extends Heap.Indexed> extends Comparable<I> {

        int getIndex();

        void setIndex(int index);
    }

}