java priorityQueue更新問題

Question

（對不起，因爲我的英語不好）我在寫一個Dijkstra算法的實現，我需要使用一個優先級隊列。 我使用Java Platform SE 6中定義的PriorityQueue。 在Java Platform SE 5中，有一種類似於Q.update（）的方法，可以在插入元素的優先級後重建優先級隊列？ （我有問題放鬆和Q.poll（）） 我需要的更新需要O（日誌n）

Answer 1

不，與PriorityQueue，沒有辦法重新堆隊列時，他們在隊列。

這是堆的通用優化。儘管刪除堆頂部並將堆中的（更新）元素重新放入堆的時間複雜度是相同的，但只需通知堆的頂部元素已更新並可能需要大約一半的時間在堆中移動。

Answer 2

更新已在優先隊列中的元素的優先級是一項重要的操作，而不提供此操作的優先級隊列或多或少沒有用處。

優先級隊列，允許爲O更新已插入的值（log n）的時間的實現看起來是這樣的：

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

這裏所使用的優先級隊列的三個小例子。

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