Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

PriorityQueue/Heap Update

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.

like image 651
kevmo314 Avatar asked Apr 03 '09 16:04

kevmo314


People also ask

How do I update my heap?

When using a min/max-heap algorithm, priorities may change. One way to handle this is to removal and insert the element to update the queue order. For priority queues implemented using arrays, this can be a performance bottleneck that seems avoidable, especially for cases when the change to priority is small.

Is PriorityQueue same as heap?

The heap provides multiple functions and operations than the priority queue. The priority queue provides queue-related functions. The heap implements abstract data types such as priority queue but priority queue does not implement heap. The priority queue is simpler than the heap data structure.

How do you update a priority queue element?

To update priority in Priority Queue, get the index of the element that you want to update the priority of and assign a new key to the element. After updating the priority of an element, we need to heapify the heap to maintain the heap data structure.

Is PriorityQueue default min-heap?

The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.


1 Answers

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());         }     } } 
like image 145
Esko Luontola Avatar answered Oct 12 '22 10:10

Esko Luontola