配對堆的自適應屬性

配對堆專為完美使用優先佇列而實現。優先佇列跟蹤一組物件的最小值，因此每次我們從佇列中取出某個元素時，它始終是最小值。使用迪傑斯特拉演算法計算圖中最短路徑時，通常會實現優先佇列。

配對堆非常完美，因為它們易於使用並且在實際應用中執行良好。具體來說，它們在攤銷時間方面運作得非常好。這意味著儘管單個操作會花費更長的時間，但佇列在整個生命週期中的所有操作的總和很快。配對堆更容易編碼，並且通常比斐波那契堆執行得更好。

配對堆具有非常簡單的屬性。每個堆都與一個物件或值相關聯。每個堆還配備了一組子堆。物件的總是大於（或小於）其子堆的值。

堆有一些基本操作 −

min(heap) – 獲取最小值。此函式非常簡單。它查詢堆的頂部值。

merge(heap1, heap2) – 合併或組合兩個堆。將具有最大值的堆新增到另一個堆的子堆。此函式也很快。

Arnab Chakraborty

更新於：2020 年 1 月 2 日

113 次瀏覽

開啟你的 職業生涯

結業即可取得認證

開始