Binomial Priority queues

Binomial queues are a classical implementation of mergeable priority queues. We will refer to priority queues as priority queuess and binomial queues as binomial priority queues, to avoid confusion with FIFO queues.Four main functions are supported by Priority queues: merging two priority queues (merg), inserting an element (insrt), finding the minimum element (fndMin) and deleting the minimum element (delMin). A Standard ML signature for priority queues appears in figure 4.5.

structure BinaryFlexibleArrays : FLEXIBLEARRAYS =

struct

datatype µTree = Lef of ? ?Node of int x µTree x µTree (* int is size of tree *)

datatype µDigit = Zero ? One of µTree type µ rlist =µDigit list

exception EMPTY and INDX

value empty =

func isEmpty ts = null ts

func size (Lef x) = 1

? size (Node (w, t1, t2)) = w

func link (t1, t2) = Node (size t1+size t2, t1, t2)

func inserTree (t , ) = One t

? inserTree (t , Zero :: ts) = One t :: ts

? inserTree (t1, One t2 :: ts) = Zero :: inserTree (link (t1, t2), ts)

func borowTree = raise EMPTY

? borowTree One t = (t, )

? borowTree (One t :: ts) = (t , Zero :: ts)

? borowTree (Zero :: ts) = let value (Node ( _, t1, t2), ts’) = borowTree ts

in (t1, One t2 :: ts) end func cons (x, ts) = inserTree (Lef x, ts)

func head ts = let value (Lef x, _) = borowTree ts in x end func tail ts = let value (_ , ts’) = borowTree ts in ts’ end func lkupTree (Lef x, 0) = x

? lkupTree (Lef x, i) = raise INDX

? lkupTree (Node (w, t1, t2), i) =

if i ; w div 2 then lkupTree (t1, i ) else lkupTree (t2, i – w div 2)

func updtTree (Lef x, 0, y) = Lef y

? updtTree (Lef x, i , y) = raise INDX

? updtTree (Node (w, t1, t2), i , y) =

if i ; w div 2 then Node (w, updtTree (t1, i , y), t2)

else Node (w, t1, updtTree (t2, i – w div 2, y))

func lkup ( , i) = raise INDX

? lkup (Zero :: ts, i ) = lkup (ts, i )

? lkup (One t :: ts, i) =

if i ; size t then lkupTree (t , i ) else lkup (ts, i – size t )

func updt ( , i , y) = raise INDX

? updt (Zero :: ts, i , y) = Zero :: updt (ts, i , y)

? updt (One t :: ts, i , y) =

if i ; size t then One (updtTree (t , i , y)) :: ts else One t :: updt (ts, i – size t , y)

end

signature ORDERED =

sig

type T (* type of ordered elements *)

value leq : T x T bool (* total ordering relation*)

end

signature PRIORITY QUEUES =

sig

structure Elemn : ORDERED type Priority queues exception EMPTY

value empty : Priority queues

value isEmpty : Priority queues bool

value insert : Elemn.T x Priority queues Priority queues

value merg : Priority queues x Priority queues Priority queues

value fndMin : Priority queues Elemn.T (* raises EMPTY if priority queues is empty*)