Macaulay2 » Documentation
Packages » EquivariantGB :: PriorityQueue
next | previous | forward | backward | up | index | toc

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

Menu

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.


The source of this document is in EquivariantGB.m2:1418:0.