Внедрить операцию 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)) 

Answer 2

Прикрепление код heapify и пирамидальной сортировки тоже ..

`

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 

`