Реализуйте операцию heapify в функциональном стиле - PullRequest
Новая
       12

Реализуйте операцию heapify в функциональном стиле

0 голосов
/ 02 января 2012

Просто интересно, есть ли способ реализовать операцию heapify в функциональном стиле?

Предположим, тип данных: 

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

Ответы [ 2 ]

6 голосов
/ 02 января 2012

Скажем, ваш тип в 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))
0 голосов
/ 08 января 2015

Прикрепление кода для heapify и heapsort тоже ..

`

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

`

...