手機站首頁散文詩歌雜文隨筆日記小小說

散文網(wǎng) » 科技 »學習 » C++ 數(shù)據(jù)結(jié)構(gòu) - 堆

C++ 數(shù)據(jù)結(jié)構(gòu) - 堆

2023-03-11 20:48 作者:DecemberFox 0人讀過 | 我要投稿

與樹相同，堆 ( Heap ) 也是一種樹形的數(shù)據(jù)結(jié)構(gòu)，本文所有堆都使用二叉堆實現(xiàn)

二叉堆

在?二叉樹?這篇文章中我們學過滿二叉樹以及完全二叉樹，而二叉堆就是一棵完全二叉樹

如果你忘記了什么是完全二叉樹可以回去看看

如下圖就是一棵二叉堆 ( 有點丑?)

我們可以稱堆的根結(jié)點 ( 1 ) 為堆頂

但是，如果堆僅僅是一個完全二叉樹就不至于把它單獨拿出來講了，堆還有一個重要的特點，堆的每個結(jié)點存儲的是以其為堆頂?shù)男碌亩娑训淖顑?yōu)值，并通過一層層的傳遞，根結(jié)點存儲的就是整棵樹的最優(yōu)值了

為什么要使用二叉堆

首先我們來看看優(yōu)先隊列，在隊列中我們曾手打過低配版的優(yōu)先隊列 ( 即在數(shù)組的基礎上，與其前一個數(shù)進行比較，在不滿足條件時交換，從而時隊頭為最優(yōu)解?)，分析復雜度可知，如果輸入的數(shù)據(jù)為下降序列，第? $i$ ?次添加數(shù)據(jù)就需要交換? $i-1$ 次，如果要添加? $n$ 次數(shù)據(jù)，總的時間復雜度就為? $O(%5Cfrac%7B(n%2B1)n%7D%7B2%7D)$ ，效率甚至不如讀入后進行一次快速排序，可謂是非常糟糕

為此，我們可以使用二叉堆來解決，并且大大提高效率

堆的種類

常見的堆有大根堆 ( 最大堆 ) 與小根堆 ( 最小堆 )，大根堆的根結(jié)點是整個堆的最大值，小根堆的根結(jié)點是整個堆的最小值

但是我們將數(shù)據(jù)放入或拿出堆中時，可能會破壞這樣的平衡，導致最小值 / 最大值不是根結(jié)點了，于是就需要使用一些操作來保持堆的形態(tài)

堆的操作

堆作為一個數(shù)據(jù)結(jié)構(gòu)，就是用來存儲，管理數(shù)據(jù)的，它有點像隊列，只允許從刪除堆頂 ( 出堆?) 和從末尾添加結(jié)點 ( 入堆 )

但是，有時添加 / 刪除了結(jié)點后，就將堆的性質(zhì)破壞了，這時我們就需要用上浮和下沉來維護堆的結(jié)構(gòu)

入堆操作

我們將下面? $n%3D8$ ?個數(shù)據(jù)依次放入一個小根堆中

并使用? $heap_i$ ?來記錄堆第? $i$ ?處的數(shù)據(jù)，使用? $tot$ 來記錄堆的最后一個地方

根據(jù)二叉樹的性質(zhì)可知

一個結(jié)點?(?非根結(jié)點?)?的父親結(jié)點為 :? $%5Clfloor%5Cfrac%7Bi%7D%7B2%7D%20%5Crfloor%20$
一個結(jié)點 (?非葉子結(jié)點 ) 的左兒子結(jié)點為 :? $2i$
一個結(jié)點?(?非葉子結(jié)點?) 的右兒子結(jié)點為 :? $2i%2B1$

先在? $top%3D1$ 的位置放入第一個數(shù) 13，這時將? $top$ 增加 1，代碼實現(xiàn)如下

再放入 5，這時，先將它放在最后一個地方 ( 即結(jié)點 $top%3D2$ ?的地方 )

這個時候，發(fā)現(xiàn)這棵樹并不滿足小根堆的性質(zhì)，需要我們進行調(diào)整，要把結(jié)點 2 往上抬，這個操作稱為上浮，對父結(jié)點進行檢測，如果父親結(jié)點的值大于自己，就將自己與父親結(jié)點的值交換，代碼實現(xiàn)如下

于是，這棵樹又重新滿足了小根堆的性質(zhì)，重新變回了堆

下一個添加的是 -3，并將其放在結(jié)點 3 的位置

這棵樹再一次不滿足小根堆的性質(zhì)，于是我們要再次對其進行上浮操作，這個時候我們對比低配版的優(yōu)先隊列發(fā)現(xiàn)，同樣的操作，二叉堆版優(yōu)先隊列僅需交換 1 次，而低配版優(yōu)先隊列需要交換 2 次，效率直接翻倍

并且，隨著二叉堆的層數(shù)不斷增加，并且在最差的情況下 ( 新加入的數(shù)為最小值?)，交換的次數(shù)僅僅為? $log_2n$ ?次，而低配版需要交換整整? $n$ 次

事實上，二叉堆每次上浮都排除了相當多的結(jié)點，這也是其更加快的原因

正確性證明

我們知道，二叉堆的堆頂存放的一定是這個堆最優(yōu)的解，如果需要進行上浮的數(shù)據(jù)要比這個堆的堆頂數(shù)據(jù)更優(yōu)，那它就一定比這個堆的其他結(jié)點的數(shù)據(jù)更優(yōu)，所以上浮是正確的

下一個放入的數(shù)據(jù)是 9，還是先放入進來

放入后，樹再次不滿足小根堆的性質(zhì)，再次進行上浮操作，但不同的是，這一次不是上浮至堆頂，而是在合適的位置停下

將全部數(shù)據(jù)放入后就就會得到下面的二叉堆 ( 可以自己先模擬建堆，然后再來看看是否正確?)

最終入堆代碼如下

時間復雜度 ( 最差 )?:? $O(log_2n)$

出堆操作

學會了添加操作，接下來學習刪除操作

前面提到在刪除時只能刪除堆頂，但是刪除完堆頂后，裂開來的兩個堆要怎么合并起來呢

還是使用上面建好的堆，依次刪除堆的堆頂

刪除堆頂后，堆就裂成了兩半，變成了這樣

這就像一個團隊沒有了領頭一樣，所以，我們要找一個臨時的領頭來代替刪除的結(jié)點，因為其他節(jié)點 ( 除最后一個結(jié)點以外的結(jié)點?) 都不好移動，所以就選擇了最后一個結(jié)點作為新的領頭

雖然現(xiàn)在兩個堆重新合并了，但是問題仍然明顯，結(jié)點 1 并不是這個堆的最優(yōu)解 ( 而是最差解 )，這時就要用到把結(jié)點 1 往下降，這個操作稱作下沉操作

不同的是，上浮操作不用選，直接與父親結(jié)點交換，可是下沉操作可以下沉到左兒子和右兒子，這時應該選擇下沉到哪里呢

思考上方的二叉堆，如果我們選擇將結(jié)點 1 下沉至其左兒子處，那么就會得到這樣二叉堆

顯然 -1 的位置是錯誤的，因為它并不比 3 號結(jié)點更優(yōu)

但如果將結(jié)點 1 下沉至其右兒子處，那么就會的到這樣的二叉堆

除了節(jié)點 3 為堆頂?shù)亩娑岩酝舛己苷?/figcaption>

所以我們要將堆頂與較小的兒子結(jié)點進行交換操作

正確性證明

在每一次下沉操作中，可以確定的是其左右子結(jié)點是其堆中的最優(yōu)解，也就是說，左右子結(jié)點為第 1 及第 2 優(yōu)的答案

顯然的，我們需要將最優(yōu)的答案放在堆頂，即選擇第 1 優(yōu)的答案并與其進行交換，每一次選擇也并不會重新影響之前的選擇，所以進行一次完整的下沉操作是正確的

將結(jié)點?3 繼續(xù)下沉，就可以得到