priority queue java example

PriorityQueue/Heap Update

Question

¿Tiene Java una manera fácil de reevaluar un montón una vez que la prioridad de un objeto en un PriorityQueue ha cambiado? No puedo encontrar ninguna señal 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

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 : eche un vistazo a este hilo: ¿ una cola de prioridad que permite una actualización de prioridad eficiente?

Answer 2

Es posible que deba implementar dicho montón usted 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 mejorar esta clase para que, en lugar del método abstracto de TheGreaterOrEqual, el orden de clasificación se base en el Comparador de Java y las interfaces Comparables, y también haga que la clase use genéricos).

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 3

Está bien. PriorityQueue of 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 hace Map . De hecho, acepta el mismo objeto varias veces.

También quería hacer que PQ ofreciera una 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í mientras estoy actualizando, solo estoy aumentando la prioridad (para mi implementación) y está usando MaxHeap, entonces estoy haciendo bubbleUp. Uno puede necesitar heapify basado en el requisito.

Answer 4

Lamentablemente, JDK''s Priority Queue no proporciona actualizaciones. Robert Sedgewick y Kevin Wayne son bien conocidos por sus cursos de algoritmos en Princeton, y también escribieron Algorithms .

Dentro de este excelente libro, proporcionan sus propias implementaciones para las estructuras de datos, incluidas las colas de prioridad actualizable, como IndexMinPQ.java

Licencia bajo GPLv3.

Answer 5

Las interfaces estándar no proporcionan 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 integrada para un estilo peek() y update() del uso de heap.

Answer 6

PriorityQueue tiene el método heapify que reordena todo el montón, el método fixUp , que promueve un elemento de mayor prioridad en el montón, y el método fixDown , que empuja un elemento de menor prioridad hacia abajo del montón. Lamentablemente, todos estos métodos son privados, por lo que no puede usarlos.

Consideraría usar el patrón Observer para que un elemento contenido pueda decirle a la cola que su prioridad ha cambiado, y la cola puede hacer algo como fixUp o fixDown dependiendo de si la prioridad aumenta o disminuye respectivamente.