1.堆的概念和性質

(1)概念

堆是一顆特殊的完全二叉樹，只是它這個樹所有的節點不大于父親節點或者所有的節點不小于父親節點，則稱為大堆或小堆
根節點最大的叫大根堆，根節點最小的叫小根堆

(2)性質：

堆中每個節點總是不大于子節點或不小于子節點
堆總是一顆完全二叉樹

邏輯結果是我們想象出來的，為了方便于我們理解，而實際中堆的存盤結構式以陣列的形式存盤
在這里插入圖片描述

選擇題：

1.下列關鍵字序列為堆的是：（）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32

首先，我們需要先把陣列畫成堆的邏輯結構
在這里插入圖片描述

2.堆的實作

(1)堆的向下調整方法

現在我們給出一個陣列，邏輯上看做一顆完全二叉樹，我們通過從根節點開始的向下調整演算法可以把它調整
成一個小堆，向下調整演算法有一個前提：左右子樹必須是一個堆，才能調整，

int a[] = {27,15,19,18,28,34,65,49,25,37};

向下調整演算法的前提是：左右子樹必須是一個堆，如果根節點的的左右子樹都不是堆怎么辦？別急，這些在后面都會講到

先把陣列畫成堆的邏輯結構
在這里插入圖片描述

1.找出左右孩子中較小那個值
2.如果小的孩子節點比父親節點要小，則跟父親節點交換，并且把原來的孩子位置當成父親，繼續向下調整，直到走到葉子節點，
如果小的孩子比父親大，則不需要調整，此時的堆已經是小堆

在這里插入圖片描述

在這里插入圖片描述

該交換的代碼為

首先我們需要直到兩個完全二叉樹的公式:

假設父親的下標為parent，則它的左孩子的下標一定為leftchild=2×parent+1，右孩子rightchild=2×parent+2

在這里插入圖片描述

該演算法的時間復雜度為O(logn)

我們給出任意一個陣列，如果左右子樹都不是小堆怎么辦？

int a[] = {27,30,40,18,28,34,65,49,25,37};

這時候我們就不能使用向下調整的方法，所以我們要想辦法把左右子樹變成兩個小堆
從倒數第一個非葉子節點，從后往前，依次作為子樹去向下調整

在這里插入圖片描述
代碼是在上面的基礎上，在加一個for回圈，所以，我們這樣我們就可以把一個無規則的陣列變成一個小堆

是的，很完美，把一個普通陣列變成了一個小根堆

那我們要把一個陣列變為一個大根堆，我們需要怎么做：

把一個陣列變為大根堆，跟上面的把陣列變為小根堆的思路一樣，只是左右子樹要恰好為大根堆

在這里插入圖片描述

同樣的，我們把上面的陣列進行調整，把它變成一個大根堆

int a[] = { 27,30,40,18,28,34,65,49,25,37 };

在這里插入圖片描述

(2)利用堆將陣列排一個升序

排序，在c語言中我們學到了一個冒泡排序，而冒泡排序的效率很低，它的時間復雜度為O(N^2)
所以我們可以利用堆的結構進行排序，看一下效率如何
首先，我們要清楚，建堆的時間復雜度為：O(N)
那么我們要排升序，需要利用的是大堆還是小堆呢？哪種效率更高呢
答案：大堆
我們先來看一下小堆的排序：
在這里插入圖片描述
那么,我們來看看建大堆來實作排升序是怎樣的呢，