Skip to main content

module util::PriorityQueue

rascal-0.34.0

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)