// Copyright 2012, University of Freiburg,
// Chair of Algorithms and Data Structures.
// Author: Hannah Bast .
// NOTE: this is a code design suggestion in pseudo-code. It is not supposed to
// be compilable in any language. You have to translate it to Java or C++
// yourself.
// Class implementing a priority queue (PQ) with its four basic operations:
// insert, getMin, deleteMin, and changeKey. Elements in the PQ are key-value
// pairs, see PriorityQueueItem.H.
// Complexity: the operations insert, deleteMin, and changeKey should all run in
// time O(log n), where n is the number of elements in the PQ before the
// operation. The operation getMin should run in constant time, indepedendent of
// the number of elements in the PQ.
public class PriorityQueue {
// PUBLIC MEMBERS.
// Create an empty PQ.
PriorityQueue();
// Insert an element into the PQ. Returns a pointer to a PQ item (which can
// be used later to change the key of that item, if desired).
PriorityQueueItem insert(int key, T value);
// Get the PQ item with the smallest key. If several items with the smallest
// key exist, return anyone of them. If the PQ is empty, return null.
PriorityQueueItem getMin();
// Delete the PQ item with the smallest key. If several items with the
// smallest key exist, delete the one that would be returned by a call to
// getMin. If the PQ is empty, do nothing.
void deleteMin();
// Change the key of the given PQ item. The item must have been obtained as
// the return value of either insert or getMin before, and it must not have
// been deleted in the meantime. Otherwise the result of this method is
// undefined.
void changeKey(PriorityQueueItem item, int newKey);
// The number of elements currently in the PQ.
int size();
// PRIVATE MEMBERS.
// Both of the following two methods assume that, before the call, the heap
// property holds everywhere, except possibly at the given position. Then,
// after the call, it will hold everywhere again.
// If the position is outside of 1..n, where n is the number of elements
// currently in the heap, do nothing.
// Repair the heap from the given array position downwards.
void repairHeapDownwards(int position);
// Repair the heap from the given array position upwards.
void repairHeapUpwards(int position);
// Swap two items in the heap and adjust their indices.
void swapItemsAndAdjustIndices( int position1, int position2);
// The heap, stored in a simple array.
// In C++ use a std::vector of pointers to PriorityQueueItem's
Array< PriorityQueueItem > heap;
}