Data Structures公開課聽課筆記-（二）堆

01-25

UCSD數據結構課第二周的課程，主要講了堆和堆的擴展，第三周是講的哈希，內容比較多，所以就把第二周的單獨拿出來了，我覺得data structure作為系列裡第二門課程明顯比第一門algorithm內容多一些。

堆是一種樹型的數據結構，定義是：1、堆總是一棵完全二叉樹，2、堆中某個節點的值總是不大於或不小於其父節點的值。

堆的特點就像堆這個詞一樣，例如平時擺在桌子上的一堆書，最頂上的書通常就是你要用到的書，如果不是，你就會把這本書放到下面；如果你需要哪本書，你就會把那本書放到最頂上，但你不會給所有書排一個使用順序堆成一個書堆。

堆的結構就是這樣，最頂上的元素就是所需要的元素，而內部的數據結構是為了保證頂上元素的正確性，而不是為了讓堆里所有的元素都是有序的。

1、堆的基本操作

堆的基本操作其實只有兩種，siftup和siftdown。以最小堆為例。

siftup：嘗試向上挪動一個節點。

1、比較該節點和父節點的大小

2、如果比父節點小，那麼該節點和父節點交換位置，交換位置後重複第一步

3、如果比父節點大，那麼說明該節點已經在合適的位置了。

def siftup(node): if node < parent_node: node,parent_node = parent_node,node siftup(parent_node)

（靈魂畫師出手，如下圖）

sift down：嘗試向下移動一個節點

1、比較該節點和兩個子節點的大小

2、如果有子節點比該節點小，那麼該節點和較小（如果兩個子節點都小）的子節點交換位置，之後重複第一步

3、如果比子節點都小，那麼說明該節點已經在合適的位置了。

def siftdown(node): next_node = node: if left_child < node: next_node = left_child if right_child < node: next_node = right_child if next_node != node: node,next_node = next_node,node siftdown(next_node)

而堆的其他操作，插入，彈出，刪除等等都是在siftup和siftdown這兩個基本操作的基礎上實現的。

插入節點：要插入的節點放在一個，能保證完全二叉樹結構的葉節點下，然後siftup這個節點，直到這個節點到達合適的位置。

彈出節點：首先彈出根節點，然後將任意一個葉節點放在根節點的位置上，再對根節點siftdown。

更改節點優先順序：更改節點優先順序後嘗試對節點siftup和siftdown，直到該節點到達合適的位置。

刪除節點：更改節點的優先順序為無窮大，然後siftup要刪除的節點。

2、最大堆，最小堆

最小堆：堆中某個節點的值總是不小於其父節點的值；最大堆：堆中某個節點的值總是不大於其父節點的值；

3、堆的數組實現

堆一定是一棵完全二叉樹，完全二叉樹的好處就是

1、樹的高度比不完全二叉樹低
2、樹可以用數組這種簡單的數據結構來實現

代價就是要維護樹的完整性。

用數組表示堆和用數組表示完全二叉樹的原理是一樣的，都是用數組索引映射樹的層數。

4、集合

可以用堆表示集合，兩個集合的union操作，也就是將兩個堆merge在一起。

判斷兩個元素在不在同一個集合里，也就是判斷兩個元素的根節點相不相同。

5、優先順序隊列問題

1、本周的作業第一道題是給出一個順序錯亂的堆，求總共需要交換多少對節點能變成一個正確的堆。

不管是從葉節點開始對每一個節點siftup，還是從根節點開始對每一個節點siftdown都可以解決這個問題。

2、第二道題是一個優先順序隊列的問題。

python中的堆是heapq，而python中非常方便的一點是，如果堆內節點的元素有多個值，可以用tuple來方便的比較。

例如用堆內節點表示一組線程要處理的任務，節點有1、任務優先順序p；2、任務時間t。在任務優先順序相同時比較任務時間，時間短的先執行。

那麼heapq中的節點可以直接以tuple的形式（p，t），因為python對tuple的比較是先比較第一個元素，再比較第二個元素，因此可以用tuple搭配heapq簡便地實現優先順序隊列。