轉自：http://eriol.iteye.com/blog/1174672

平常，我們用堆最常見的就是隨機地加入元素，隨機地取最大值或最小值。這些基本的操作C++中的priority_queue和set都能很好的完成，而且C++中還有一個make_heap，效率較前面2個會更高。而且前面提到的STL都是采用紅黑樹實現(xiàn)的，很具有穩(wěn)定性。

?

上面的堆雖然使用簡單，但功能上還是有些局限。比如前面提到的堆都只能實現(xiàn)刪除最值并沒有辦法刪除指定的值。而且一般STL中的堆都是采用數(shù)據存儲的，但父親節(jié)點和兒子節(jié)點需要交換時，我們需要拷貝所存儲的整個數(shù)據單元，但數(shù)據單元較大時，拷貝的效率就低了。因此，這里介紹一中堆變種，在堆中引入了映射。

?

?

定義

?

具有映射功能的堆稱為雙向映射堆。又因其常常是在二分堆的基礎上實現(xiàn)的，所以也常常叫映射二分堆。

?

?

特點

?

映射二分堆其與普通堆不同的地方是它的節(jié)點并不真正保存數(shù)據單元本身，而是保存指向數(shù)據單元的指針。因此當需要交換父子節(jié)點的數(shù)據時，我們可以避免拷貝大量數(shù)據所消耗的時間。同時，映射二分堆還有一個功能，它可以根據具體的數(shù)據單元的索引來刪除該單元，即使這個單元不是堆中的最值。

?

?

實現(xiàn)

?

在實現(xiàn)時，我們可以用數(shù)字 H[] 存儲數(shù)據單元，然后采用數(shù)組 ind[i]=j 表示 H[i] 存放的是索引號為 j 的數(shù)據，mp[j]=i 表示索引索引為 j 的元素存儲在 H[i] 中，這樣就可以實現(xiàn)雙向映射了。

?

(1) 插入堆，我們只需要將插入的元素放在堆尾，然后逐級調整，這個跟普通的二叉堆一樣。

?

(2) 刪除最值，也跟普通的二叉堆一樣，先把堆中最后一個元素與最值對調，然后再調整堆。

?

(3) 刪除固定索引的數(shù)據單元。我們可以先通過 mp[i]，找到其在 H[] 中存放的位置，然后該位置的值跟堆最后一個元素對調，接著從該節(jié)點向上調整堆，此時得到的還不是一個正規(guī)的堆，還需要重新堆整個堆進行從上到下調整。

?

上面的3中操作中都提到了堆的調整，在調整時我們不需要拷貝數(shù)據單元，我們只需交換 ind[] 和 mp[] 2個數(shù)組的對應值即可。

總結

以上是生活随笔為你收集整理的映射二分堆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。