— You must enter your student ID number here: uXXXXXXX
module Heap where
— Type declarations for Heap.
— DO NOT EDIT THESE TYPE DECLARATIONS.
data Tree a = Node a [Tree a] deriving (Show, Eq)
— | height
— given a Tree as input,
— return the height of the Tree, where the height is the number of edges
— to its most distant leaf node.
—
— Examples:
—
— >>> height (Node 10 [])
— 1
—
— >>> height (Node 10 [Node 9 [], Node 7 [], Node 8 [] ])
— 2
—
— >>> height (Node 10 [Node 9 [Node 6 []], Node 7 [Node 4 [], Node 2 []], Node 8 [Node 6 [Node 1 []]]])
— 4
—
— >>> height (Node 10 [Node 9 [ ], Node 7 [Node 4 [], Node 2 []], Node 8 [Node 6 [Node 1 []]]])
— 4
—
height :: Tree a -> Int
height (Node _ []) = undefined — TODO
— | isBalanced
— given a Tree as input,
— return True if the Tree is balanced. The tree is balanced if the difference between the longest
— path to a leaf and the shortest path to a leaf is no greater than 1.
—
— Examples:
—
— >>> isBalanced (Node 10 [])
— True
—
— >>> isBalanced (Node 10 [Node 9 [], Node 7 [], Node 8 [] ])
— True
—
— >>> isBalanced (Node 10 [Node 9 [Node 6 []], Node 7 [Node 4 [], Node 2 []], Node 8 [Node 6 [Node 1 []]]])
— True
—
— >>> isBalanced (Node 10 [Node 9 [ ], Node 7 [Node 4 [], Node 2 []], Node 8 [Node 6 [Node 1 []]]])
— False
—
isBalanced :: Tree a -> Bool
isBalanced (Node _ []) = undefined — TODO
— | isHeap
— given a Tree as input,
— return True if the Tree is a Heap in the sense that
— – All children of a node are less than or equal to the parent value;
— – The tree is balanced
—
— Examples:
—
— >>> isHeap (Node 10 [])
— True
—
— >>> isHeap (Node 10 [Node 9 [], Node 7 [], Node 8 [] ])
— True
—
— >>> isHeap (Node 10 [Node 9 [Node 6 []], Node 7 [Node 4 [], Node 2 []], Node 8 [Node 6 [Node 1 []]]])
— True
—
— >>> isHeap (Node 10 [Node 9 [ ], Node 7 [Node 4 [], Node 2 []], Node 8 [Node 6 [Node 1 []]]])
— False
—
— >>> isHeap (Node 5 [Node 9 [Node 6 []], Node 7 [Node 4 [], Node 2 []], Node 8 [Node 6 [Node 1 []]]])
— False
—
isHeap :: Ord a => Tree a -> Bool
isHeap (Node _ []) = undefined — TODO