-- Heap code from QuickSpec examples.
-- https://github.com/nick8325/quickspec/blob/0.9.6/examples/Heaps.hs
--
-- Copyright (c) 2009-2014, Nick Smallbone
-- https://github.com/nick8325/quickspec/blob/0.9.6/LICENSE (BSD3 license)
module Heap where

data Heap a = Nil | Branch Int a (Heap a) (Heap a) deriving Show

instance Ord a => Eq (Heap a) where
  h1 == h2 = toList h1 == toList h2

toList :: Ord a => Heap a -> [a]
toList Nil = []
toList h   = findMin h : toList (deleteMin h)

fromList :: Ord a => [a] -> Heap a
fromList = foldr insert Nil

null :: Heap a -> Bool
null Nil = True
null _ = False

findMin :: Heap a -> a
findMin (Branch _ x _ _) = x

insert :: Ord a => a -> Heap a -> Heap a
insert x h = merge h (branch x Nil Nil)

deleteMin :: Ord a => Heap a -> Heap a
deleteMin (Branch _ _ l r) = merge l r

branch :: Ord a => a -> Heap a -> Heap a -> Heap a
branch x l r | npl l <= npl r = Branch (npl l + 1) x l r
             | otherwise = Branch (npl r + 1) x r l

merge :: Ord a => Heap a -> Heap a -> Heap a
merge Nil h = h
merge h Nil = h
merge h1@(Branch _ x1 l1 r1) h2@(Branch _ x2 l2 r2)
 | x1 <= x2 = branch x1 (merge l1 h2) r1
 | otherwise = merge h2 h1

npl :: Heap a -> Int
npl Nil = 0
npl (Branch n _ _ _) = n