在haskell中将树转换为堆

Question

我需要在Haskell中使用堆树实现优先级队列,例如:

给出一个清单: [3,2,7,8,4,1,9]

3 is the  main root
2 is its left leaf
7 is its right leaf

8 is the left leaf of 2
4 is the right leaf of  2

1 is the left leaf of 7
9 is the right leaf of 7

如果我想堆树,那就像这样:

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

我们以这样的列表结束: [9,7,8,2,4,1,3]

并且9是队列中具有最高编号(优先级)的元素.

我需要这样做:

• insert h e将元素插入e堆中h(在最后位置)
• delete h 删除具有最高优先级的元素(在我们的示例9中)
• heapify h 将树堆起来.

但我的问题是heapify功能,我甚至不知道从哪里开始.这就是我要求线索或建议的原因.

Answer 1

module Heapify where

我们使用树型

data Tree a = Leaf a | Node (Tree a) a (Tree a) 
   deriving Show

和示例树

ourTree = Node (Node (Leaf 8) 2 (Leaf 4))    3    (Node (Leaf 1) 7 (Leaf 9))

并找出如何堆积它.

你在图片中的描述

顶级节点

左子树

正确的子树

Heapified？

在这种情况下,结果确实是一个堆,但是这个方法不是进行堆化的标准方法,并且没有概括(据我所知)确保你有堆的东西.感谢威尔内斯指出这一点.

我们应该如何堆积？

如果每个父节点不小于其子节点,则树满足堆属性.(它没有说明子节点的比较大小.)

Heapification实际上有点像插入排序,因为你从低端开始,逐步向上工作,在你引入它们时将小元素拖回原位.

第1步:修改左右子树

第2步:此节点:检查是否应下拉最高值

第3步:如果是这样,再次在那边堆积

步骤1,2和4只是递归调用,所以让我们专注于顶级节点:

顶级节点

我们需要(a)看到子树顶部的值,(b)能够替换它.

atTop :: Tree a -> a
atTop (Leaf a) = a
atTop (Node _ a _) = a

replaceTop :: Ord a => Tree a -> a -> Tree a
replaceTop (Leaf _) a = Leaf a
replaceTop (Node l _ r) a = heapify (Node l a r)

请注意厚脸皮的前向引用heapify？当我们替换树的顶部节点时,我们需要重新堆积它以确保它仍然是树.

现在让我们看看如有必要,如何在左侧进行调整.

如果左子树的顶部topL大于a节点的值,则必须这样做.如果<=我们不需要做任何事情,那么请保持节点不变.

adjustLeft :: Ord a => Tree a -> Tree a
adjustLeft (Leaf a) = Leaf a   -- But we shouldn't ask to do this. 
adjustLeft  node@(Node l a r) 
     | topL <= a = node
     | otherwise = Node (replaceTop l a) topL r
         where topL = atTop l

在右边:

现在让我们在必要时调整右侧.这完全相同.

adjustRight :: Ord a => Tree a -> Tree a
adjustRight (Leaf a) = Leaf a   -- But we shouldn't ask to do this. 
adjustRight  node@(Node l a r) 
     | topR <= a = node
     | otherwise = Node l topR (replaceTop r a) 
         where topR = atTop r

让我们看看其中的一些工作:

*Heapify> ourTree
Node (Node (Leaf 8) 2 (Leaf 4)) 3 (Node (Leaf 1) 7 (Leaf 9))
*Heapify> atTop ourTree
3

向下拉到左边还是右边？

如果当前值属于树下方的较低值,我们需要将其向左或向右拉,通过将其与较大的值进行交换.我们选择较大的值,因此我们知道它超过了左子树中的最高值.

doTop :: Ord a => Tree a -> Tree a
doTop (Leaf a) = Leaf a
doTop node@(Node l a r) 
    | atTop l > atTop r = adjustLeft node
    | otherwise         = adjustRight node

请记住adjustLeft并对adjustRightheapify进行递归调用.

返回堆积

所以要堆积,我们只是

heapify :: Ord a => Tree a -> Tree a
heapify (Leaf a) = Leaf a
heapify (Node l a r) = doTop (Node (heapify l) a (heapify r))

好的,这很容易.我们来测试一下:

*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))