Turning a tree into a heap in haskell -

i need make implementation of priority queue heap tree in haskell, example:

given list: [3,2,7,8,4,1,9]

3  main root 2 left leaf 7 right leaf  8 left leaf of 2 4 right leaf of  2  1 left leaf of 7 9 right leaf of 7 

if want heapifiy tree this:

7 > 3 exchange them 8 > 2 exchange them 8 > 7 exchange them 9 > 3 exchange them 9 > 8 exchange them 

we end list this: [9,7,8,2,4,1,3]

and 9 element highest number (priority) in our queue.

i need this:

• insert h e inserts element e in heap h (in last position)
• delete h removes element highest priority (in our example 9)
• heapify h heapifies tree.

but problem heapify function, dont know start. that's why im asking clues or advice.

module heapify 

let's use tree type

data tree = leaf | node (tree a) (tree a)     deriving show 

and example tree

ourtree = node (node (leaf 8) 2 (leaf 4))    3    (node (leaf 1) 7 (leaf 9)) 

and work out how heapify it.

your description in pictures

top node

left subtree

right subtree

heapified?

in case, result indeed heap, method isn't standard way of doing heapification, , doesn't generalise (as far can tell) make sure have heap. credit will ness pointing out.

how should heapify?

a tree satisfies heap property if each parent node no smaller child nodes. (it says nothing compararive sizes of child nodes.)

heapification works bit insertion sort, in start @ low end, , work gradually up, dragging small elements place introduce them.

step 1: heapify left , right subtrees

step 2: node: check if top value should pulled down

step 3: if so, heapify @ side again

steps 1,2 , 4 recursive calls, let's concentrate on top node:

top node

we need (a) see value @ top of subtrees , (b) able replace it.

attop :: tree -> attop (leaf a) = attop (node _ _) = 

replacetop :: ord => tree -> -> tree replacetop (leaf _) = leaf replacetop (node l _ r) = heapify (node l r) 

notice cheeky forward reference heapify? when replace top node of tree, need re-heapify make sure it's still tree.

now let's see how adjust @ left hand side if necessary.

it's necessary if top of left subtree, topl, larger value a @ node. if it's <= don't need anything, leave node alone.

adjustleft :: ord => tree -> tree adjustleft (leaf a) = leaf   -- shouldn't ask this.  adjustleft  node@(node l r)       | topl <= = node      | otherwise = node (replacetop l a) topl r          topl = attop l 

and @ right:

now let's adjust @ right hand side if necessary. works same.

adjustright :: ord => tree -> tree adjustright (leaf a) = leaf   -- shouldn't ask this.  adjustright  node@(node l r)       | topr <= = node      | otherwise = node l topr (replacetop r a)           topr = attop r 

let's see of working:

*heapify> ourtree node (node (leaf 8) 2 (leaf 4)) 3 (node (leaf 1) 7 (leaf 9)) *heapify> attop ourtree 3 

pull down left or right?

if current value belongs lower down tree, need pull down left or right side, swapping larger value of two. pick larger value know it's more top value in left subtree.

dotop :: ord => tree -> tree dotop (leaf a) = leaf dotop node@(node l r)      | attop l > attop r = adjustleft node     | otherwise         = adjustright node 

remember adjustleft , adjustright make recursive call heapify.

return of heapification

so heapify,

heapify :: ord => tree -> tree heapify (leaf a) = leaf heapify (node l r) = dotop (node (heapify l) (heapify r)) 

ok, easy. let's test it:

*heapify> ourtree node (node (leaf 8) 2 (leaf 4)) 3 (node (leaf 1) 7 (leaf 9)) *heapify> heapify ourtree node (node (leaf 2) 8 (leaf 4)) 9 (node (leaf 1) 7 (leaf 3))