java priorityQueue problème de mise à jour

Question

(désolé pour mon mauvais anglais) J'écris une implémentation de Dijkstra algoritm et j'ai besoin d'utiliser une file d'attente prioritaire. J'utilise PriorityQueue comme défini dans Java Platform SE 6. Est-il possible d'utiliser une méthode comme Q.update() dans Java Platform SE 5 pour reconstruire la file d'attente prioritaire dans le cas où les priorités de ses éléments ont changé depuis leur insertion? (J'ai un problème et se détendre Q.poll()) j'ai besoin que la mise à jour prend O (log n)

Answer 1

Non, avec un PriorityQueue, il n'y a aucun moyen de re-tas d'éléments alors qu'ils sont dans la file d'attente .

Ceci est une optimisation courante pour les tas. Bien que la complexité de la suppression du haut du tas et de la remise d'un élément (mis à jour) dans le tas soit du même ordre, il faut environ la moitié du temps pour avertir le tas que l'élément supérieur a été mis à jour. être déplacé dans le tas.

Answer 2

La mise à jour de la priorité d'un élément déjà dans la file d'attente prioritaire est une opération importante et une file d'attente prioritaire ne proposant pas cette opération est plus ou moins inutile.

Une mise en œuvre d'une file d'attente prioritaire qui permet la mise à jour d'une valeur déjà insérée dans O (log n) ressemble à ceci:

/** 
* PriorityQueue with updatePriority and item concept. 
* Makes use of a min heap. 
* 
* @author Chris Stamm 
* @version 6.10.2013 
*/ 

import java.util.*; 

public class PQueue<E extends Comparable<E>> { 
public static class PQItem<E extends Comparable<E>> implements Comparable<PQItem<E>> { 
    private E m_data; 
    private int m_index; 

    public PQItem(E data, int index) { 
     m_data = data; 
     m_index = index; 
    } 

    public int compareTo(PQItem<E> item) { 
     return m_data.compareTo(item.m_data); 
    } 

    public E getData() { 
     return m_data; 
    } 

    public void setIndex(int index) { 
     m_index = index; 
    } 

    public int getIndex() { 
     return m_index; 
    } 
} 

private ArrayList<PQItem<E>> m_array; 

public PQueue() { 
    m_array = new ArrayList<PQItem<E>>(); 
} 

/** 
* O(n) 
*/ 
public PQueue(Collection<? extends E> c) { 
    m_array = new ArrayList<PQItem<E>>(c.size()); 

    // copy elements 
    int j = 0; 
    for(E e: c) { 
     m_array.add(new PQItem(e, j++)); 
    } 

    // create heap 
    final int s = m_array.size(); 
    int l2 = s/2 - 1; 
    for (int i = l2; i >= 0; i--) { 
     siftDown(i); 
    } 
} 

public int size() { 
    return m_array.size(); 
} 

public boolean isEmpty() { 
    return m_array.isEmpty(); 
} 

/** 
* O(log n) 
*/ 
public PQItem<E> add(E data) { 
    int s = size(); 
    PQItem<E> item = new PQItem(data, s); 
    m_array.add(item); 
    siftUp(s); 
    return item; 
} 

/** 
* O(log n) 
*/ 
public E removeFirst() { 
    int size = size(); 
    if (size == 0) return null; 
    if (size == 1) return m_array.remove(0).getData(); 

    int last = size - 1; 
    // swap a[first] with a[last] 
    PQItem<E> t = m_array.get(0); 
    E data = t.getData(); 
    set(0, m_array.get(last)); 
    set(last, t); 
    // remove last 
    m_array.remove(last); 
    // heapify 
    siftDown(0); 
    return data; 
} 

public void clear() { 
    m_array.clear(); 
} 

public PQItem<E> getItem(int i) { 
    return (i >= 0 && i < size()) ? m_array.get(i) : null; 
} 

public PQItem<E> getFirstItem() { 
    return getItem(0); 
} 

public PQItem<E> getNextItem(PQItem<E> item) { 
    if (item == null) return null; 
    int index = item.getIndex() + 1; 
    return (index < size()) ? m_array.get(index) : null; 
} 

/** 
* O(log n) 
*/ 
public void updatePriority(PQItem<E> item) { 
    int pos = item.getIndex(); 
    if (pos > 0) { 
     // check heap condition at parent 
     int par = (pos - 1)/2; 
     if (m_array.get(par).compareTo(m_array.get(pos)) > 0) { 
      siftUp(pos); 
      return; 
     } 
    } 
    int son = pos*2 + 1; 
    if (son < size()) { 
     // check heap condition at son 
     if (m_array.get(pos).compareTo(m_array.get(son)) > 0) { 
      siftDown(pos); 
     }   
    } 
} 

private int set(int pos, PQItem<E> item) { 
    int oldIndex = item.getIndex(); 
    item.setIndex(pos); 
    m_array.set(pos, item); 
    return oldIndex; 
} 

/** 
* sift down at position pos. 
* O(log n) 
*/ 
private void siftDown(int pos) { 
    final int end = size() - 1; 
    int son = pos*2 + 1; 

    while (son <= end) { 
     // son ist der linke Sohn 
     if (son < end) { 
      // pos hat auch einen rechten Sohn 
      if (m_array.get(son).compareTo(m_array.get(son + 1)) > 0) son++; 
     } 
     // son ist der grössere Sohn 
     if (m_array.get(pos).compareTo(m_array.get(son)) > 0) { 
      // swap a[pos] with a[son] 
      PQItem<E> t = m_array.get(pos); 
      set(pos, m_array.get(son)); 
      set(son, t); 
      pos = son; 
      son = 2*pos + 1; 
     } else { 
      return; 
     } 
    } 
} 

/** 
* sift up at position pos 
* O(log n) 
*/ 
private void siftUp(int pos) { 
    int par = (pos - 1)/2; // parent 

    while(par >= 0) { 
     if (m_array.get(par).compareTo(m_array.get(pos)) > 0) { 
      // swap a[par] with a[pos] 
      PQItem<E> t = m_array.get(par); 
      set(par, m_array.get(pos)); 
      set(pos, t); 
      pos = par; 
      par = (pos - 1)/2; 
     } else { 
      return; 
     }    
    } 
} 
} 

Et voici trois petits exemples d'utilisation de la file d'attente prioritaire.

static void showMinHeap() { 
    Integer[] values = { 7, 9, 6, 3, 5, 1, 2, 8, 4, 0}; 
    PQueue<Integer> pq = new PQueue<Integer>(Arrays.asList(values)); 

    int lev = 1, i = 0; 
    PQueue.PQItem<Integer> item = pq.getFirstItem(); 
    while(item != null) { 
     if (i == lev) { 
      System.out.println(); 
      lev <<= 1; 
      i = 0; 
     } 
     System.out.print(item.getData()); 
     System.out.print(' '); 
     i++; 
     item = pq.getNextItem(item); 
    }  
    System.out.println(); 
} 

static void heapSort() { 
    Integer[] values = { 7, 9, 6, 3, 5, 1, 2, 8, 4, 0}; 
    PQueue<Integer> pq = new PQueue<Integer>(Arrays.asList(values)); 

    for(int i=0; i < values.length; i++) { 
     System.out.print(pq.removeFirst()); 
     System.out.print(' '); 
    } 
    System.out.println(); 
} 

static void testNodes() { 
    class Node implements Comparable<Node> { 
     private int m_key; 

     public Node(int k) { 
      m_key = k; 
     } 

     public void updateKey() { 
      m_key *= 2; 
     } 

     public int compareTo(Node v) { 
      return (m_key == v.m_key) ? 0 : (m_key < v.m_key) ? -1 : 1; 
     } 

     public String toString() { 
      return String.valueOf(m_key); 
     } 
    } 

    PQueue<Node> pq= new PQueue<Node>(); 
    Random rand = new Random(7777); 
    final int size = 20; 

    for (int i = 0; i < size; i++) { 
     Node v = new Node(rand.nextInt(size)); 
     pq.add(v); 
    } 
    for (int i = 0; i < size; i++) { 
     // change key and update priority 
     PQueue.PQItem<Node> item = pq.getItem(rand.nextInt(pq.size())); 
     item.getData().updateKey(); 
     pq.updatePriority(item); 

     // remove and show first 
     System.out.println(pq.removeFirst()); 
    } 
    System.out.println(); 
}