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

new topic     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu