Skip to main content

module util::PriorityQueue


A PriorityQueue datatype and associated functions.


import util::PriorityQueue;


import util::Math;
import List;


Priority queues maintain (priority, value) pairs in sorted order. They are implemented using a Binomial heap Priority queue are, for instance, used to implement shortest path algorithms.

Provides the following functions:




Currently, both priority and associated value ("payload") have to be integers. This will be generalized.

data BinomialTree

data BinomialTree  
= binomialTree(int priority, // priority of this tree
int val, // payload
int degree, // degree of tree
list[BinomialTree] children // subtrees

function addSubTree

BinomialTree addSubTree(BinomialTree p, BinomialTree q)

function mergeTree

BinomialTree mergeTree(BinomialTree p, BinomialTree q)

function toString

str toString(BinomialTree T)

data PriorityQueue

data PriorityQueue  
= priorityQueue(list[BinomialTree] trees, // trees in the heap
int minIndex // index of minimal tree

function mkPriorityQueue

PriorityQueue mkPriorityQueue()

PriorityQueue mkPriorityQueue(int priority, int val)

function isEmpty

bool isEmpty(PriorityQueue Q)

function insertElement

PriorityQueue insertElement(PriorityQueue Q, int priority, int val)

function findMinimum

int findMinimum(PriorityQueue Q)

function extractMinimum

tuple[int, int, PriorityQueue] extractMinimum(PriorityQueue Q)

function toString

str toString(PriorityQueue Q)

function add

list[BinomialTree] add(list[BinomialTree] heap, BinomialTree t)

function mergeQueue

PriorityQueue mergeQueue(PriorityQueue p, PriorityQueue q)