目錄
滿二叉樹:??
完全二叉樹:
堆是一種特殊的完全二叉樹:
我們可以以數組的方式存儲堆。
父節點和子節點下標關系的推導:
1.使用數學歸納法證明n2 + 1 = n0:
2.使用邊和節點的關系證明n2 + 1 = n0:
我們來看看堆有哪些方法:
向下調整算法:
向上調整算法:
堆排序:
向下調整建堆:
向上調整建堆:
topk問題:
滿二叉樹:??
定義:
一棵深度為?kk?的滿二叉樹,是指所有非葉子節點都有左右子節點,且所有葉子節點都在最底層的二叉樹。換句話說,滿二叉樹的每一層都被完全填滿。
完全二叉樹:
定義:
一棵深度為?kk?的完全二叉樹,除了最后一層外,其他層的節點都被完全填滿,且最后一層的節點盡可能靠左排列。完全二叉樹允許最后一層不滿,但空缺只能出現在右側。
堆是一種特殊的完全二叉樹:
滿足以下性質:
-
完全二叉樹結構:堆的邏輯結構是一棵完全二叉樹(所有層除最后一層外都被填滿,且最后一層的節點盡可能靠左排列)。
-
堆序性質(Heap Property):
-
最大堆(Max Heap):每個節點的值 ≥ 其子節點的值(根節點是最大值)。
-
最小堆(Min Heap):每個節點的值 ≤ 其子節點的值(根節點是最小值)。
-
當我們給完全二叉樹的每個節點從上到下從左到右編個序號。
我們可以發現父節點和子節點的序號之間存在一些關系。
parent*2 + 1 = childleft(左子節點)
parent*2 + 2 = childright(右子節點)
(child-1)/2 = parent.(這是C語言的計算)
當我們知道父節點的下標,就能知道子節點的下標,知道子節點的下標也可以知道父節點的下標。
我們可以以數組的方式存儲堆。
注意:
1.只有向下取整的計算規則(當x是小數時,取不大于x的最大整數)才能用數組的形式存儲完全二叉樹。
2.只有完全二叉樹適合用數組來存儲
父節點和子節點下標關系的推導:
證明這個關系我們用到了一個二叉樹的結論:n2 + 1= n0:度為2的節點個數比度為0的節點個數少一個。
而這個結論也是可以證明的
1.使用數學歸納法證明n2 + 1 = n0:
由于第一個節點滿足n2+1 = n0;
假設第k個節點也滿足n2+1 = n0;
我們要證明第k+1個節點也滿足n2 +1 = n0;
第k+1個節點有兩種情況:
情況1:它是一個左子節點:那么度為0的父節點就變成了度為1的節點,同時多出一個度為0的子節點。(度為0的節點個數不變)
情況2:它是一個右子節點:那么度為1的父節點就變成了度為2的節點,同時多出一個度為0的子節點(度為0的節點個數和度為2的節點個數同時+1)。
2.使用邊和節點的關系證明n2 + 1 = n0:
像下面這樣一個二叉樹,一共有6條邊,n0+n1+n2-1(除了根節點外的每個節點都貢獻一條邊)
而邊的個數同時也等于n2*2+n1(度為2的節點個數*2 + 度為1的節點個數)
列等式:n0+n1+n2-1 = n2*2+n1
化簡得:n0 = n2+1
知道了堆可以用數組來存儲,
我們來看看堆有哪些方法:
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;void HeapInit(Heap* php);
// 堆的銷毀
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的刪除
void HeapPop(Heap* hp);
// 取堆頂的數據
HPDataType HeapTop(Heap* hp);
// 堆的數據個數
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
初始化和銷毀不用說,其中基本的方法有插入、刪除和取堆頂數據。以及堆的數據個數和堆的判空。
在插入數據或者刪除數據的時候,為了保證數據始終是以堆的形式在存儲,我們引出了向下調整算法和向上調整算法:
向下調整算法:
從一個根開始,父節點和左右子節點中較大的(或者較小的)那個比較,如果父節點小(或者大)就交換,否則就退出循環。
void AdjustDown(HPDataType* a, int n, int root)
{int parent = root;int child = parent * 2 + 1;while (child < n){//建大堆//找出左右孩子中比較大的那個if ((child + 1 < n) && (a[child] < a[child + 1])){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}
向上調整算法:
從一個子節點開始,和它的父節點比較,不符合堆的關系就交換,符合時退出循環。
在實際實現向上調整算法的時候循環判斷很容易寫錯:
如果這里寫成了parent >= 0就會導致程序死循環:當parent = 0時,child更新后為0,parent再更新還是為0.
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)//這個判斷條件很容易寫錯{if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}
堆排序:
堆排序的思想就是,對一個無序的數組,首先進行建堆(保證堆頂的數據是最大的或者最小的)。把堆頂的數據交換到堆尾,然后向下調整一遍。同時更新堆尾下標。
void HeapSort(int* a, int n)
{//向下調整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//建好堆之后,交換堆頂和堆尾的數據,向下調整。int end = n - 1;//先創建一個變量記錄排序到哪個位置了while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
這里的建堆方式有兩種:一種是向上調整建堆,另一種是向下調整建堆。我們可以分析一下這兩種方式的時間復雜度。
完全二叉樹向下調整建堆和向上調整建堆最好情況下,最后一層只有一個節點,最壞情況下最后一層是滿的,由于我們要分析時間復雜度,所以要選擇滿二叉樹來分析。
向下調整建堆:
從下到上,保證調整的時候只有根不是堆的關系。向下調整建堆可以從第一個非葉子節點開始。
向下調整建堆的時間復雜度是O(N)。
向上調整建堆:
從上到下,保證上層是堆的關系。
向上調整建堆的時間復雜度是N*logN
topk問題:
從n個元素中選出最大(最小)的k個元素。
先建堆,選最大元素建小堆(比榜尾大就入榜),選最小元素建大堆(比榜尾小就入榜)。
void CreateNDate()//創建N個數據的方法
{int n = 10000;FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");exit(1);}srand((unsigned int)time(NULL));for (int i = 0; i < n; i++){fprintf(fin, "%d\n", rand() % 100000 + 1);}fclose(fin);
}
void PrintTopK(int k)
{//入榜條件是比榜尾要大,所以要和榜尾比較int* topk = (int *)malloc(sizeof(int) * k);//打開文件讀取數據FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen fail\n");exit(1);}int num = 0;//入k個數據for (int i = 0; i < k; i++){fscanf(fout, "%d", &num);topk[i] = num;}//向下調整建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, k, i);}//循環判斷數據是否入榜while (fscanf(fout, "%d", &num) != EOF){if (num > topk[0]){topk[0] = num;AdjustDown(topk, k, 0);}}fclose(fout);for (int i = 0; i < k; i++){printf("%d ", topk[i]);}
}