機能スタイルで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やヒープソートのためのコードをアタッチ

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

Answer 2

..

`

import qualified Data.Char as C 
import qualified Data.List as L 
import qualified Data.Map as M 

type Value = Int 
data Heap = Nil 
      | Node Heap Value Heap 

instance Show Heap where 
    show = showHeap 0 

type Indent = Int 

tabs :: Int -> String 
tabs n = replicate n '\t' 

showHeap :: Indent -> Heap -> String 
showHeap indent Nil = tabs indent 
showHeap indent (Node l v r) = concat $ (map (\s -> "\n" ++ (tabs indent) ++ s) [showHeap (indent+1) l, show v, showHeap (indent+1) r]) 

height :: Heap -> Int 
height Nil = 0 
height (Node l _ r) = 1 + max (height r) (height l) 

emptyHeap :: Heap 
emptyHeap = Nil 

heapify :: [Int] -> Heap 
heapify vs = heapify' vs emptyHeap 
    where 
    heapify' :: [Value] -> Heap -> Heap 
    heapify' [] hp = hp 
    heapify' (v:vs) hp = heapify' vs (insertIntoHeap v hp) 

insertIntoHeap :: Value -> Heap -> Heap 
insertIntoHeap v' Nil = Node Nil v' Nil 
insertIntoHeap v' (Node l v r) | v' <= v = if (height l <= height r) 
              then (Node (insertIntoHeap v l) v' r) 
              else (Node l v' (insertIntoHeap v r)) 
           | otherwise = if (height l <= height r) 
              then (Node (insertIntoHeap v' l) v r) 
              else (Node l v (insertIntoHeap v' r)) 

removeMin :: Heap -> (Value, Heap) 
removeMin (Node l v r) = (v, mergeHeaps l r) 

removeNMinFromHeap :: Heap -> Int -> [Value] 
removeNMinFromHeap Nil _ = [] 
removeNMinFromHeap _ 0 = [] 
removeNMinFromHeap h n = (m:(removeNMinFromHeap h' (n-1))) 
    where 
    (m, h') = removeMin h 

mergeHeaps :: Heap -> Heap -> Heap 
mergeHeaps Nil h = h 
mergeHeaps h Nil = h 
mergeHeaps l@(Node l1 v1 r1) r@(Node l2 v2 r2) | v1 <= v2 = (Node (mergeHeaps l1 r1) v1 r) 
               | otherwise = Node l v2 (mergeHeaps l2 r2) 


heapSort :: [Value] -> [Value] 
heapSort xs = removeNMinFromHeap heaped (length xs) 
    where 
    heaped = heapify xs 

input :: [Value] 
input = [3,2,1,4,3,2,10,11,2,5,6,7] 

input2 :: [Value] 
input2 = concat $ replicate 2 [3,2,1,4,3,2,10,11,2,5,6,7] 

h1 :: Heap 
h1 = heapify input 

`