Das Aktualisieren der Priorität eines bereits in der Prioritätswarteschlange vorhandenen Elements ist eine wichtige Operation, und eine Prioritätswarteschlange, die diese Operation nicht anbietet, ist mehr oder weniger nutzlos.
/**
* 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;
}
}
}
}
Und hier sind drei kleine Beispiele für die Prioritätswarteschlange verwenden.
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();
}
Der Punkt einer Prioritätswarteschlange ist, dass die Priorität des Elements nicht geändert werden soll. Wenn dies der Fall ist, sollten Sie es herausziehen und es mit der neuen Priorität einfügen. Welche mögliche Anforderung haben Sie, dass Sie eine bestimmte begrenzte Laufzeit benötigen? Ich bezweifle ernsthaft, dass Sie in der Lage sein werden, O (logN) für den Wiederaufbau einer Warteschlange zu bekommen ... Sie werden glücklich sein, O (N) – Falmarri
möglich Duplikate von [Update Java PriorityQueue, wenn seine Elemente Priorität ändern] (http://stackoverflow.com/questions/1871253/updating-java-priorityqueue-when-its-elements-change-priority) – Raedwald