haskell - 在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))

并找出如何堆放它。

您在图片中的描述

顶部节点

左子树

右子树

变胖了？

在这种情况下，结果确实是一个堆，但这种方法不是进行堆化的标准方法，并且不能概括（据我所知）确保你有一个堆的东西。感谢Will Ness指出这一点。

我们应该如何堆积？

如果每个父节点不小于其子节点，则树满足堆属性。（它没有说明子节点的比较大小。）

堆化实际上有点像插入排序，因为你从低端开始，然后逐渐向上工作，在引入小元素时将它们拖回原位。

Step 1：Heapify左右子树

第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并adjustRight递归调用 heapify。

堆化的返回

所以为了heapify，我们只是

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