一，樹的概念
1，樹的概念
樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合。
把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
有一個特殊的結點，稱為根結點，根結點沒有前驅結點
除根結點外，其余結點被分成M(M>0)個互不相交的集合
T1、T2、……、Tm，其中每一個集合Ti(1<= i <= m)又是一棵結構與樹類似的子樹。每棵子樹的根結點有且只有一個前驅，可以有0個或多個后繼
因此，樹是遞歸定義的
注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構
2，樹的相關概念
3，二叉樹的概念
一棵二叉樹是結點的一個有限集合，該集合:
1. 或者為空
2. 由一個根結點加上兩棵別稱為左子樹和右子樹的二叉樹組成
1. 二叉樹不存在度大于2的結點
2. 二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹
注意：對于任意的二叉樹都是由以下幾種情況復合而成的：?
特殊的二叉樹：
1. 滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是 說，如果一個二叉樹的層數為K，且結點總數是 ，則它就是滿二叉樹。
2. 完全二叉樹：完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K 的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對 應時稱之為完全二叉樹。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
?
?節點與高度關系
設高度為h，節點個數為N??
?
4,堆的概念
如果有一個關鍵碼的集合K = { ， ， ，…， }，把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個一維數組中，并滿足： = 且 >= ) i = 0，1， 2…，則稱為小堆(或大堆)。將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆。 ?
物理：數組
邏輯：完全二叉樹
堆的性質
堆中某個結點的值總是不大于或不小于其父結點的值；
堆總是一棵完全二叉樹。
二，堆的實現
老規矩建立三個文件 Heap.c Heap.h Test.c
?1，堆的結構
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;2，堆的初始化
void HPInit(HP* php);
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}3，堆的銷毀
void HPDestroy(HP* php);
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}4，數據的交換
?void Swap(HPDataType* p1, HPDataType* p2);
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}5，向上調整（小堆為例）
void AdjustUp(HPDataType* a, int child);
void AdjustUp(HPDataType* a, int child)
{// 初始條件// 中間過程// 結束條件int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}條件while (parent >= 0) 不準確，由于child==0時，parent = (child - 1) / 2;是整型還是為0，故可以實現?
6，堆的插入
void HPPush(HP* php, HPDataType x);
判斷空間是否足夠
if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}插入數據
php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;調整數據
AdjustUp(php->a, php->size - 1);總代碼
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}?
?
?
??
7，堆的刪除（刪除堆頂）
挪動覆蓋刪除堆頂數據，會導致堆的關系錯誤
可以將堆頂數據和堆尾數據互換，這樣其兩個左右子樹還是小堆，然后使用向下調節算法?
?
void HPPop(HP* php);
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size-1]);php->size--;AdjustDown(php->a, php->size, 0);
}8，向下調整（小堆為例）?
?void AdjustDown(HPDataType* a, int n, int parent);
void AdjustDown(HPDataType* a, int n, int parent)
{// 先假設左孩子小int child = parent * 2 + 1;while (child < n) // child >= n說明孩子不存在，調整到葉子了{// 找出小的那個孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}?9，取堆頂數據
HPDataType HPTop(HP* php);
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}10，判斷堆是否為空
bool HPEmpty(HP* php);
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}?三，堆的應用
利用堆排序
向上調整建堆
for (int i = 1; i < n; i++){AdjustUp(a, i);}?向下調整建堆
for (int i = (n-1-1)/2; i >= 0; i--){AdjustDown(a, n, i);}完整代碼
void HeapSort(int* a, int n)
{// 降序，建小堆// 升序，建大堆/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*/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)?
向上調整
?
向上調整建堆O(N*logN)
n個數找最大的前K個
方法一
建一個N個數的大堆? O(N)
pop k次 O(K*logN)
方法二
用前k個數 建一個小堆 O(K)
剩下的數跟堆頂數據比較，如果比堆頂數據大，就替代堆頂數據進堆（覆蓋跟位置然后向下調整）
O(log K*(N-K))
