堆

堆？

堆(Heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵完全二叉樹的數組對象。

——選自“百度百科”

堆的特性？

• 堆中某個節點的值總是不大于（大根堆）或不小于（小根堆）其父節點的值；
• 堆總是一棵完全二叉樹。

堆的作用？

• 堆支持插入、刪除、查找最大（小）值的操作。

堆的操作？

終于到了堆的操作了。
堆有5種操作，上移（$up$）、下移（$down$）、插入（$insert$）、刪除（$delete$）、建堆。

規定：
h數組表示堆里面的值
swap函數表示把堆兩個元素交換
num表示堆中元素個數

上移（$up$）

上移操作：當我們插入進來的數（一般是最后一個數）使得堆不符合特性時，我們就每次把它與它的父親比較，然后上移；

//我們以小根堆為例： void up(int x){//把x這個位置上移while (x>0&&h[x]<h[x/2]){swap(x,x/2);//交換x/=2;//very important！}return; }

下移（$down$）

下移操作：當我們的堆不符合特性（一般是堆頂）時，我們就每次把它與它的兒子比較，然后下移；

//我們以小根堆為例： void down(int x){//把x這個位置下移while (x*2<=num&&h[x]>h[x/2]||x*2+1<=num&&h[x]>=h[x*2+1]){int y=x*2;if (y+1<=num&&h[y]>h[y+1]) y++;//盡量選小的換swap(x,y);//交換x=y;//very important！}return; }

插入（$insert$）

插入操作：很多時候我們需要插入元素進堆里面，于是乎，我們就num++并把它插入到堆的最后一個位置；

void insert(int x){//插入xh[++num]=x;up(num);return }

刪除（$delete$）

刪除操作：很多時候我們需要刪除堆里面的最大（小）值，于是乎，我們就先把堆頂彈出。
很多人就問了：彈出后不久沒堆頂了嗎?
不著急“孩子，慢慢來”。
這時我們就采取將最后一個元素放到堆頂，然后下移（自己感性理解一下）。

void del(int x){//刪除xh[1]=h[num--];down(1);return }

建堆

講了那么久，終于到了建堆時刻了！
對于建堆，我們有兩種方法：

方法一：

for (int i=1;i<=n;i++){scanf("%d",&x);insert(x); }

時間復雜度：$O(nlo{g}_{2}n)$（很顯然吧）

方法二

for (int i=1;i<=n;i++){scanf("%d",&h[i]); } for (int i=n/2;i>0;i--)down(i);

時間復雜度：$O(n)$，感興趣的可以自己去證明一下，嘿嘿；

總結

這篇文章就這么結束了，感謝大家的支持！下一篇我將講關與堆的一些例題，讓大家多了解堆。
我可能是為數不多的手打堆的人了，很多人都在用優先隊列（感興趣的可以自己學一下），可能是因為當年我是P黨所以我才手打堆吧 ！
如果這篇文章有問題，歡迎大家踴躍“投稿”！
哦，別忘了我的blog
下一章，堆（二）堆的應用

總結

以上是生活随笔為你收集整理的堆（一）堆是啥子的全部內容，希望文章能夠幫你解決所遇到的問題。

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