在功能样式中实现heapify操作

Question

只是想知道有没有办法在功能样式中实现heapify操作？

假设数据类型是:

type 'a heap = Empty | Node of  'a * 'a heap * 'a heap

Answer 1

在Haskell中说出你的类型

data Heap a = Empty | Node a (Heap a) (Heap a)

假设我们想要一个最大堆.让我们从一个moveDown修复几乎堆的函数开始,这个堆可能有一个不正确的根.

moveDown :: (Ord a) => Heap a -> Heap a
moveDown Empty = Empty
moveDown h@(Node x Empty Empty) = h
moveDown (Node x (Node y Empty Empty) Empty) = Node larger (Node smaller Empty Empty) Empty
where
    (larger, smaller) = if x >= y then (x,y) else (y,x)
moveDown h@(Node x le@(Node y p q) ri@(Node z r s) )
    | (x >= y) && (x >= z) = h
    | (y >= x) && (y >= z) = Node y (moveDown (Node x p q)) ri
    | (z >= x) && (z >= y) = Node z le (moveDown (Node x r s))

请注意,由于堆的结构,如果节点具有左子节点但没有右子节点,则左子节点没有子节点.此外,节点不可能有正确的子节点但没有左子节点.

现在heapify很简单:

heapify :: (Ord a) => Heap a -> Heap a
heapify Empty = Empty
heapify (Node x p q) = moveDown (Node x (heapify p) (heapify q))