Display program code

fib_heap.pl : Fibonacci heap priority queue
Optimal Fibonacci heap implementation based on [Fredman & Tarjan, J. ACM 34(3), 1987]. Maintain a priority queue which contains item-priority pairs.
Items are integers > 0, priorities are any numeric type. An item-priority pair can be added, its priority can be decreased, and the item with the lowest priority can be extracted (find+remove).

How to use:
The following operations are supported:
insert(I,P): add item I with priority P
extract_min(I,P): returns minimal priority pair I-P and removes it
decr(I,NP): decreases the priority of I to the new value NP (only if NP is smaller than the old priority)
decr_or_ins(I,P): decreases the priority of I, or inserts it if it is not in the queue
Data is represented internally as:
item(I,P,Rank,Parent,Mark): a node in the Fibonacci heap. Parent=0 for roots. See literature for Rank and Mark.
min(I,P): current minimal element
Internal operations are:
findmin: [extract_min] find the new minimal element
ch2rt(I): [extract_min] convert the children of I to roots
decr(I,NP,R,P,M): [decr] re-inserts an item in a decrease operation, respecting heap order
mark(I): [decr] mark I, and if necessary, cut it off and mark its parent

See also:
Fibonacci heaps are used in dijkstra.pl
Reference paper: Dijkstra's Algorithm with Fibonacci Heaps: An Executable Description in CHR. Jon Sneyers, Tom Schrijvers and Bart Demoen. WLP 2006.

Program: Change the code, then submit!

Console: Enter query or select example from below, then submit and wait for answer!

Select example query: 

WebCHR help - CHR Website - (c) Copyrights Martin Kaeser Uni Ulm 2007