PriorityQueue/Heap Update

Question

¿Tiene Java una forma fácil de reevaluar un montón una vez que la prioridad de un objeto en un PriorityQueue ha cambiado? No puedo encontrar ningún signo de ello en Javadoc, pero tiene que haber una manera de hacerlo de alguna manera, ¿no? Actualmente estoy eliminando el objeto y luego volviéndolo a agregar, pero obviamente es más lento que ejecutar la actualización en el montón.

Answer 1

Puede que tenga que poner en práctica un montón tales ti mismo. Debe tener algún control sobre la posición del elemento en el montón, y algunos métodos para subir o bajar el elemento cuando ha cambiado su prioridad.

Hace algunos años escribí tal montón como parte de un trabajo escolar. Empujar un elemento hacia arriba o hacia abajo es una operación O (log N). Lanzo el siguiente código como dominio público, por lo que puede usarlo de la forma que desee. (Es posible que desee para mejorar esta clase de manera que en lugar del método isGreaterOrEqual abstraer el orden de clasificación se basaría en las interfaces de comparadores y comparable de Java, y también haría que los genéricos de uso de la clase.)

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

Dependiendo de la implementación de la estructura de datos, puede que no haya una manera más rápida. La mayoría de los algoritmos PQ/Heap no proporcionan una función de actualización. La implementación de Java puede no ser diferente. Tenga en cuenta que aunque una eliminación/inserción hace que el código sea más lento, es poco probable que resulte en código con una complejidad de tiempo de ejecución diferente.

Editar: echar un vistazo a este tema: A priority queue which allows efficient priority update?

Answer 3

Las interfaces estándar don' t proporcionar una capacidad de actualización. Usted ha usado un tipo personalizado que implementa esto.

Y tienes razón; aunque la complejidad de la gran O de los algoritmos que usan un montón no cambia cuando quita y reemplaza la parte superior del montón, su tiempo de ejecución real puede casi duplicarse. Me gustaría ver una mejor compatibilidad incorporada para un estilo peek() y update() de uso de heap.

Answer 4

PriorityQueue tiene la heapify método que re-ordena todo el montón, el método fixUp, que promueve un elemento de mayor prioridad hasta el montón, y el método fixDown, que empuja un elemento de menor prioridad por el montón. Lamentablemente, todos estos métodos son privados, por lo que no puede usarlos.

lo consideraría utilizando el patrón Observador de modo que un elemento contenido puede decir la cola que su prioridad ha cambiado, y la cola se puede hacer algo como fixUp o fixDown dependiendo de si la prioridad aumenta o disminuye, respectivamente.

Answer 5

Correcto. PriorityQueue de Java no ofrece un método para actualizar la prioridad y parece que la eliminación lleva tiempo lineal ya que no almacena objetos como claves, como lo hace Map. De hecho, acepta el mismo objeto varias veces.

También quería hacer PQ ofreciendo la operación de actualización. Aquí está el código de muestra usando genéricos. Cualquier clase que sea Comparable se puede usar con ella.

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

Aquí durante la actualización, lo único que estoy aumentando la prioridad (para mi aplicación) y está utilizando MaxHeap, por lo que estoy haciendo bubbleUp. Uno puede necesitar heapify basado en el requisito.