PriorityQueue -- an efficient mutable priority queue implementation

Description

A priority queue is a data structure for storing a collection of totally ordered objects and keeping track of the minimum. This binomial heap implementation allows for efficiently adding a new element to the queue, accessing or deleting the minimum element, or merging two queues. Efficiently means time logarithmic in the size of the queue, or better.

i1 : Q = priorityQueue {3,7,1,5}

o1 = PriorityQueue{...4...}

o1 : PriorityQueue

i2 : min Q

o2 = 1

i3 : deleteMin Q;

i4 : insert(Q,2);

i5 : min Q

o5 = 2

i6 : R = priorityQueue {4,6,8};

i7 : QR = mergePQ(Q,R);

i8 : length QR

o8 = 7

Methods that use an object of class PriorityQueue :

"deleteMin(PriorityQueue)" -- see deleteMin -- deletes the minimum element of the queue
insert(PriorityQueue,Thing) -- insert a new element into the queue
length(PriorityQueue) -- returns the number of elements in the queue
"mergePQ(PriorityQueue,PriorityQueue)" -- see mergePQ -- merges two queues
min(PriorityQueue) -- return the minimum element of the queue
"pop(PriorityQueue)" -- see pop -- returns the minimum element of the queue and deletes it

For the programmer

The object PriorityQueue is a type, with ancestor classes MutableHashTable < HashTable < Thing.

priorityQueue -- create a new PriorityQueue
insert(PriorityQueue,Thing) -- insert a new element into the queue
min(PriorityQueue) -- return the minimum element of the queue
deleteMin -- deletes the minimum element of the queue
pop -- returns the minimum element of the queue and deletes it
mergePQ -- merges two queues
length(PriorityQueue) -- returns the number of elements in the queue

PriorityQueue -- an efficient mutable priority queue implementation

Description

Methods that use an object of class PriorityQueue :

For the programmer

Menu