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