1. A little know data structure I'm teaching here...
Hi all,
I'm using the so called "binomial queues" as an example of algorithm analysis
and design in my university course here. I have programmed it for my students
to see it completely specified, and thought maybe somebody would find it
interesting and (who knows) useful...
The idea is that binomial queues are a good implementation of priority queues
because they allow you to merge 2 queues faster than the normal heap based
implementations. Priority queues are fundamental to many algorithms in
simulation, operating system implementation, and graph manipulation. Hope
you enjoy it and let me know if some terrible bug evaded me (surely)...
----- CODE BEGINS HERE -----
------------------------------------------------------------------------------
-- Binomial queue module
-- 1997, Carlos Gonzalia, Argentina, South America
-- version 0.1
-- this code is hereby put in public domain, but you take full
-- responsibility for its use or modifications
-- bugs, comments, questions: gonzalia at criba.edu.ar (till june 6 only)
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- General constants and functions defined for readability
-- Boolean constants
constant FALSE = 0
constant TRUE = 1
-- Comparison functions
function lt(object x, object y)
return compare(x,y)=-1
end function
function gt(object x, object y)
return compare(x,y)=1
end function
-- Sequence functions
function rest(sequence x)
return x[2..length(x)]
end function
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- Binomial tree data type
-- Abstract definition:
-- a one-node tree is a binomial tree of height 0
-- attaching to a binomial tree of height k-1 another binomial tree of
-- height k-1 as rightmost son gives a height k binomial tree, if the
-- heap order property is still satisfied
-- (aside: a tree satisfies the heap order property if and only if for
-- every node x, if x has a parent, then the key in the parent of x
-- is smaller or equal to the key in x)
-- Implementation:
-- as a non-empty sequence, whose first element is the root of the
-- binomial tree, and whose second to last elements (if they are
-- present) are its binomial tree sons, also sequences, in the
-- order of their increasing heights
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- root returns the key in the root of its binomial tree argument
-- (note t is declared as sequence since Euphoria does not support mutual
-- recursion, which would be needed for it to be a binomial_tree)
function root(sequence t)
return t[1]
end function
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- binomial_tree returns 0 (false) if its sequence argument is not a valid
-- binomial tree, and k+1 if it is, where k is the height of the tree
-- (note that binomial trees are by definition non-empty)
-- this function takes O(n) time in the worst case
type binomial_tree(sequence x)
integer previous, check_i
if length(x)<=1 then
return length(x)
end if
previous = 0
for i=2 to length(x) do
check_i = binomial_tree(x[i])
if previous>=check_i or gt(root(x),root(x[i])) then
return FALSE
end if
previous = check_i
end for
return length(x)
end type
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- merge_tree returns the binomial tree resulting from merging its two
-- binomial tree arguments
-- this function always takes O(1) time
function merge_tree(binomial_tree s, binomial_tree t)
if lt(root(s),root(t)) then
return append(s,t)
else
return append(t,s)
end if
end function
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- Binomial queue data type
-- Abstract definition:
-- a binomial queue is a collection of binomial trees, such that there is
-- at most one tree of any possible height
-- Implementation:
-- as a sequence of binomial_tree's, in ascending order of their heights
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- binomial_queue returns 1 (true) or 0 (false), depending on its sequence
-- argument being a valid binomial queue or not
-- (note that it is perfectly possible to have an empty binomial queue)
-- this function takes O(n) time in the worst case
global type binomial_queue(sequence x)
integer previous, check_i
previous = 0
for i=1 to length(x) do
check_i = binomial_tree(x[i])
if previous>=check_i then
return FALSE
end if
previous = check_i
end for
return TRUE
end type
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- the empty binomial queue
global constant empty_binom_queue = {}
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- find_min_bq returns the minimum element in the binomial queue
-- this function takes O(log n) time in the worst case
-- (note that using find_min_bq on an empty binomial queue is senseless
-- and causes an error)
global function find_min_bq(binomial_queue q)
object min
min = root(q[1])
for i=2 to length(q) do
if gt(min,root(q[i])) then
min = root(q[i])
end if
end for
return min
end function
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- merge_bq returns the binomial queue resulting from the merge of its two
-- binomial queue arguments
-- this function takes O(log n) time in the worst case
global function merge_bq(binomial_queue p, binomial_queue q)
binomial_queue rest_merge
if length(p)=0 or length(q)=0 then
return p & q
elsif length(p[1])<length(q[1]) then
return prepend(merge_bq(rest(p),q), p[1])
elsif length(q[1])<length(p[1]) then
return prepend(merge_bq(p,rest(q)), q[1])
else
rest_merge = merge_bq(rest(p),rest(q))
return merge_bq({merge_tree(p[1],q[1])},rest_merge)
end if
end function
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- insert_bq returns the binomial queue resulting from inserting its object
-- argument into its binomial queue argument
-- this function takes O(log n) time in the worst case, but O(1) in average
global function insert_bq(object x, binomial_queue q)
return merge_bq(q,{{x}})
end function
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- delete_min_bq returns the binomial queue resulting from deleting the
-- minimum object in the queue
-- (note that using delete_min_bq on an empty binomial queue is senseless
-- and causes an error)
-- this function takes O(log n) time in the worst case
global function delete_min_bq(binomial_queue q)
integer min
binomial_queue except_min
min = 1
for i=2 to length(q) do
if gt(root(q[min]),root(q[i])) then
min = i
end if
end for
except_min = q[1..min-1] & q[min+1..length(q)]
return merge_bq(rest(q[min]),except_min)
end function
------------------------------------------------------------------------------
----- CODE ENDS HERE -----
Carlos Gonzalia, Universidad Nacional del Sur, Argentina, South America
gonzalia at criba.edu.ar
