Skip to main content

module util::PriorityQueue

rascal-Not specified

A PriorityQueue datatype and associated functions.

Usage​

import util::PriorityQueue;

Dependencies​

import util::Math;
import List;

Description​

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:

Examples​

Benefits​

Pitfalls​

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)