Aktualizacja PriorityQueue/Heap

Question

Czy Java ma łatwy sposób na ponowną ocenę sterty po zmianie priorytetu obiektu w PriorityQueue? Nie mogę znaleźć żadnego znaku tego w Javadoc, ale musi być jakiś sposób, aby to zrobić jakoś, prawda? Obecnie usuwam obiekt, a następnie ponownie go dodaję, ale jest to oczywiście wolniejsze od uruchamiania aktualizacji na stercie.

Answer 1

może zaistnieć potrzeba wykonania takiej sterty samodzielnie. Musisz mieć pewne uchwyty do pozycji przedmiotu w stercie i niektóre metody, aby przesunąć element w górę lub w dół, gdy jego priorytet się zmienił.

Kilka lat temu napisałem taką kupę jako część pracy szkolnej. Przesuwanie elementu w górę lub w dół jest operacją O (log N). Uwalniam następujący kod jako domenę publiczną, więc możesz go używać w dowolny sposób. (Być może chcesz udoskonalić tę klasę tak, że zamiast abstrakcyjnej metody isGreaterOrEqual kolejność sortowania będzie polegać na interfejsach Javy komparatora i porównywalne, a także pozwoliłoby na rodzajowych użyć klasy.)

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

W zależności od implementacji struktury danych, może nie być szybszej metody. Większość algorytmów PQ/heap nie zapewnia funkcji aktualizacji. Implementacja Java może nie być inna. Zauważ, że chociaż polecenie remove/insert powoduje spowolnienie kodu, jest mało prawdopodobne, aby otrzymało kod o różnym stopniu złożoności.

Edit: rzucić okiem na ten wątek: A priority queue which allows efficient priority update?

Answer 3

Standardowe interfejsy don” t zapewnić możliwość aktualizacji. Użyłeś niestandardowego typu, który to implementuje.

I masz rację; Chociaż złożoność dużych algorytmów wykorzystujących stertę nie zmienia się po usunięciu i zastąpieniu wierzchołka sterty, ich faktyczny czas działania może prawie podwoić się. Chciałbym zobaczyć lepszą wbudowaną obsługę stylu sterty w stylu peek() i update().

Answer 4

kolejka priorytetowa jest sposób heapify który ponownie sortuje cały stos, sposób fixUp, która wspiera element o wyższym priorytecie górę stosu i sposób fixDown, które popycha element niższym priorytecie dół sterty. Niestety wszystkie te metody są prywatne, więc nie możesz z nich korzystać.

Pomyślę przy użyciu wzorca Observer, tak aby zawierały element może powiedzieć, że jego priorytetem kolejki uległa zmianie, a kolejki może wtedy coś zrobić jak fixUp lub fixDown zależności czy priorytet odpowiednio zwiększona lub zmniejszona.

Answer 5

Zgadza się. PriorityQueue Java nie oferuje metody aktualizacji priorytetu i wygląda na to, że usunięcie zabiera czas liniowy, ponieważ nie zapisuje obiektów jako kluczy, tak jak robi to Map. Faktycznie akceptuje ten sam obiekt wiele razy.

Chciałem również wprowadzić aktualizację oferty PQ. Oto przykładowy kod używający generycznych. Każda klasa, która jest porównywalna, może być z nią używana.

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

Tutaj podczas aktualizacji zwiększam tylko priorytet (dla mojej implementacji) i używam MaxHeap, więc robię bubbleUp. Ktoś może potrzebować zestalić na podstawie wymagań.