從堆樹中刪除根元素

此元素位於樹的根部。如果我刪除它，我剩下兩個獨立的子樹。

data Heap a = Empty 
      | Node a (Heap a) (Heap a)

類型的功能是：

removeMin :: Heap a -> (a, Heap a)

它應該返回樹並刪除了最低。

我應該輔助功能，以建立一個新的樹，還是有更快的方法來做到這一點？

來源

2015-02-08 skills

我碰巧知道在被發現堆LC Paulson針對工作程序員*的ML，包括您正在討論的二進制堆的版本。如果您想了解更多關於函數式編程的堆，我建議您閱讀Chris Okasaki撰寫的* Purely Functional Data Structures *。他涵蓋了左堆，堆放堆，二項堆，傾斜二項堆和自舉堆（Brodal-Okasaki堆）。 – dfeuer 2015-02-08 04:13:48

你應該建立一個適當的功能，以建立新的樹，但不必擔心，它不會表現不佳。 GHC可以優化這種用例，這個操作可以像你想要的那樣快（包括大的，甚至無限的（遞歸的）數據結構）。

我知道你可以自己創建這樣的輔助功能嗎？這很簡單 - 無論如何，如果遇到麻煩，我可以稍後再寫。

來源

2015-02-08 02:43:41

我想構建函數，如果你能提供一些提示來指導我，我將非常感激！ – skills 2015-02-08 02:57:09

你的類型，如書面，提出了一些問題：

問：你從removeMin Empty輸出？

答：從零開始無法生成a，所以結果應該包含在Maybe中。
問：如果我把(+)，(-)和(*)在Heap (Int -> Int -> Int)，哪一個應該由removeMin退換嗎？

答：不是所有的數據類型有一個排序（值得注意的是，功能缺乏一個），所以是有意義的要求數據類型有Ord實例。

因此，更新後的類別變爲：

removeMin :: Ord a => Heap a -> Maybe (a, Heap a)

現在考慮個案情況：

Empty沒有分元素：
```
removeMin Empty = Nothing 
```
如果一個分支是空的，其餘的堆是另一個分支
```
removeMin (Node a Empty r) = Just (a, r) 
removeMin (Node a l Empty) = Just (a, l) 
```
說服自己，這適用於Node a Empty Empty。
如果沒有分支是空的，那麼新的最小分鐘元素必須是分支之一的根。

在所得Heap分支是較大的元件的剛分支，並且較小的元件的分支，具有其最小除去。

幸運的是，我們已經有一個幫手，可以從Heap中刪除最小值！
```
removeMin (Node a [email protected](Node la _ _) [email protected](Node ra _ _)) = Just (a, Node mina maxN minN') 
    where (minN, maxN) = if la <= ra then (l,r) else (r,l) 
     Just (mina, minN') = removeMin minN 
```

現在，雖然這將產生一個有效的堆，它不一定是最好的算法，因爲它不能保證產生平衡堆。一個平衡不佳的堆並不比鏈表好，給你O(n)插入和刪除時間，其中平衡堆可以給你O(log n)。

來源

2015-02-08 03:16:44 rampion

想想這樣：刪除頂層節點後，剩下兩堆。所以，你需要實現（遞歸）合併兩個堆，像

merge :: (Ord a) => Heap a -> Heap a -> Heap a

你也可以實現一個獨異實例Heap

instance (Ord a) => Monoid (Heap a) where 
    mempty = Empty 
    mappend = -- the merging function

來源

2015-02-08 09:56:32

從堆樹中刪除根元素

回答

相關問題