Binomial.hs (588B)
1 {-# OPTIONS_GHC -fno-warn-orphans #-} 2 3 module Heap.Binomial where 4 5 import qualified Okasaki.Heap.Binomial as B 6 import Test.QuickCheck 7 import Test.Tasty (TestTree) 8 import Test.Tasty.QuickCheck (testProperty) 9 10 -- binomial trees, heaps both have invariants 11 12 -- tree 13 14 -- * tree of rank r should have 2 ^ r nodes 15 -- * tree of rank r isbinomial a node with r children, with each child 16 -- t_i having rank r - i 17 -- * children are maintained in decreasing order of rank 18 -- * elements are stored in heap order 19 20 -- heap 21 22 -- * no two trees have same rank 23 -- * list is in increasing order of rank 24