
  0 | module PairingHeap
  1 | 
  2 | import Heap
  3 | 
  4 | %default total
  5 | 
  6 | export
  7 | data PairingHeap a = E | T a (List (PairingHeap a))
  8 | 
  9 | mutual
 10 |   mergePairs : Ord a => List (PairingHeap a) -> PairingHeap a
 11 |   mergePairs [] = E
 12 |   mergePairs [h] = h
 13 |   mergePairs (h1 :: h2 :: hs) = merge (merge h1 h2) (mergePairs hs)
 14 | 
 15 |   export
 16 |   Heap PairingHeap where
 17 |     empty = E
 18 |     isEmpty E = True
 19 |     isEmpty _ = False
 20 | 
 21 |     insert x h = merge (T x []) h
 22 | 
 23 |     merge h E = h
 24 |     merge E h = h
 25 |     merge h1@(T x hs1) h2@(T y hs2) =
 26 |       if x < y then T x (h2 :: hs1) else T y (h1 :: hs2)
 27 | 
 28 |     findMin E = assert_total $ idris_crash "empty heap"
 29 |     findMin (T x hs) = x
 30 | 
 31 |     deleteMin E = assert_total $ idris_crash "empty heap"
 32 |     deleteMin (T x hs) = assert_total $ mergePairs hs
 33 |