PriorityQueue / Mise À Jour Du Tas
Java a-t-il un moyen facile de réévaluer un tas une fois que la priorité d'un objet dans un PriorityQueue a changé? Je n'en trouve aucun signe dans Javadoc, mais il doit y avoir un moyen de le faire d'une manière ou d'une autre, Non? Je suis en train de supprimer l'objet puis de le rajouter, mais c'est évidemment plus lent que d'exécuter la mise à jour sur le tas.
6 réponses
Vous devrez peut-être implémenter un tel tas vous-même. Vous avez besoin d'avoir une poignée à la position de l'élément dans le tas, et quelques méthodes pour pousser l'élément vers le haut ou vers le bas lorsque sa priorité a changé.
Il y a quelques années, j'ai écrit un tel tas dans le cadre d'un travail scolaire. Pousser un élément vers le haut ou vers le bas est une opération O(log N). Je libère le code suivant en tant que Domaine public, de sorte que vous pouvez l'utiliser de n'importe quelle façon. (Vous voudrez peut-être améliorer cette classe afin qu'au lieu de l'abstrait méthode isGreaterOrEqual l'ordre de tri reposerait sur le comparateur de Java et les interfaces comparables, et ferait également en sorte que la classe utilise des génériques.)
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());
}
}
}
PriorityQueue a la méthode heapify Qui re-trie le tas entier, la méthode fixUp, qui favorise un élément de priorité supérieure dans le tas, et la méthode fixDown, qui pousse un élément de priorité inférieure dans le tas. Malheureusement, toutes ces méthodes sont privées, vous ne pouvez donc pas les utiliser.
J'envisagerais d'utiliser le modèle D'observateur pour qu'un élément contenu puisse indiquer à la file d'attente que sa priorité a changé, et la file d'attente peut alors faire quelque chose comme fixUp ou fixDown selon si la priorité a augmenté ou diminué respectivement.
Les interfaces standard ne fournissent pas de capacité de mise à jour. Vous avez utilisé un type personnalisé qui implémente cela.
Et vous avez raison; bien que la complexité big-O des algorithmes qui utilisent un tas ne change pas lorsque vous supprimez et remplacez le haut du tas, leur temps d'exécution réel peut presque doubler. Je voudrais voir un meilleur support intégré pour un style peek() et update() d'utilisation du tas.
C'est vrai. PriorityQueue de Java n'offre pas de méthode pour mettre à jour la priorité et il semble que la suppression prend du temps linéaire car elle ne stocke pas les objets en tant que clés, comme le fait Map. Il accepte en fait le même objet plusieurs fois.
Je voulais aussi faire une opération de mise à jour PQ offrant. Voici l'exemple de code utilisant des génériques. Toute classe Comparable peut être utilisée avec elle.
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;
}
}
Ici, lors de la mise à jour, Je ne fais qu'augmenter la priorité (pour mon implémentation) et il utilise MaxHeap, donc je fais bubbleUp. On peut avoir besoin de heapify basé sur l'exigence.
Selon l'implémentation de la structure de données, il peut ne pas y avoir de moyen plus rapide. La plupart des algorithmes PQ / heap ne fournissent pas de fonction de mise à jour. L'implémentation Java peut ne pas être différente. Notez que bien qu'un remove / insert rende le code plus lent, il est peu probable qu'il en résulte un code avec une complexité d'exécution différente.
Edit : jetez un oeil à ce thread: une file d'attente prioritaire qui permet une mise à jour prioritaire efficace?
Malheureusement, la file D'attente prioritaire de JDK ne fournit pas de mises à jour. Robert Sedgewick et Kevin Wayne sont bien connus pour leurs cours d'algorithmes à Princeton, et ils ont également écrit Algorithms .
Dans cet excellent livre, ils fournissent leurs propres implémentations pour les structures de données, y compris les files d'attente prioritaires , telles que IndexMinPQ.java
Sous licence GPLv3.