數據結構練手05 關於堆的up策略和down策略實現

堆，是一個相當重要的數據結構，它是優先隊列，堆排序，Dijkstra等算法的實現保證！

堆的主要特性是：

1、根結點是最大/最小的，而這個主要的區別，就是實現比較操作時是less or　greater， 因此可以使用純虛化 比較接口，把實現放到子類。 附： STL中采用的是模板默認參數的方法實現。

2、需要兩個表示大小的變量來標定堆or數組的大小。因為pop操作因讓堆的有效長度變小，而數組的長度不變。

3、堆的插入操作一般是插入到數組的末尾，這裡最好用vector， 因為它可以在常數時間內尾插入數據且能夠動態生長。

類定義
子類定義

要保證這個heapity特性，（假定是討論最大堆）一般有兩種方式：從根到葉(down) 和 從葉到根(up)，這兩種實現各有優缺點。我們先說下各種操作的文字表述：

<<算法導論>>中采用了down的策略，即比較本結點，左右結點，得到最大值的下標索引，若不是最大索引不是本結點，則交換本結點和最大索引，接著用最大索引實現遞歸操作。

downheapity策略

StL中采用了是up的策略，僅需層層比較和父節點的大小，最多到根節點。。

upheapity策略

---

另外，在建堆操作中，若采用down策略，則可以從index= lenArray/2 的位置進行downHeapity(index)一直遞減到根結點就行。

建堆的down策略

而采用up策略，則從index = lenArray-1的位置遞減到 lenArray/2的位置，中間一直調用upHeapity（index）就行。

建堆的up策略

---

我們對堆進行pop操作時，一般來說要保留根結點的值用於最後的返回。實現中我們還需要將根結點和尾結點的值進行交換。這裡繼續說下down策略和up策略的做法。

down策略時，由於前一步已經交換了根結點和尾結點，且調整了堆大小的長度，這樣，我們就可以從索引為堆大小一半的位置開始，遞減到根，一直調用 downheapity(index)就行。

pop操作的down策略

up策略是，就比較麻煩點了，需要將交換後的根結點下放到某個小值的位置，然後再調用次upheapity保證堆特性的滿足。這個實現起來比較討厭，要判斷一些邊界條件。

pop操作的up策略

---

而對於堆排序，則就是遍歷調用pop n-1次就行。

堆排序

---

對於元素的插入來說，那肯定是StL的up占優了。因為up策略就是從尾結點開始向父節點進行比較，最多比較到根節點。 而若采用down策略，則從堆大小一半的位置遞減到根，其中一直調用downheapity（index）操作。

insert的down策略和up策略

---

因此，這裡我們可以總結下使用堆時候的策略：

• 之前我的總結有問題，今天反思了下，若都從一半堆大小開始遞減到根，那麼時間復雜度挺大的。其實所有的操作都采取down策略更易理解。
• 對於從(size-1)/2還是size/2開始，我覺得還是從(size-1)/2更好，這樣循環代碼可以修改下，且也能避免上面所誤解的地方

     insert_down 和 pop_down 中的
  
           p = parent (totalSize-     ( p !=          p =      downheapity(p);

 

使用堆的時候，一定要注意是采用數組長度還是堆長度。我們可以總結下：，同時； ，同時要注意調整堆長度水位

測試代碼：

測試代碼