簡介

堆是一種重要的數據結構，是一種完全二叉樹，（二叉樹的內容后面會出），
堆分為大小堆，大堆，左右結點都小于根節點，（又稱子節點和父節點），
小堆則反過來，可以用靜態數組/順序表實現

公式

已知某節點下標 i ，（根節點下標為0），

• 左孩子節點為 2*i+1
• 右孩子節點為 2*i+2
• 父節點 （ i - 1 ）/ 2

建立堆

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int HPTypeDate;
typedef struct {HPTypeDate* a;HPTypeDate size;HPTypeDate capacity;
}HP;

將元素插入a里面，size表示堆里面的元素個數，避免浪費內存，滿了就開辟

void HeapInit(HP* php);
void HeapPush(HP* php, HPTypeDate x);
void Adjustup(HPTypeDate* a, int child);
void swap(HPTypeDate* a, HPTypeDate* b);
void HeapPrint(HP* php, HPTypeDate n);
HPTypeDate HPTop(HP* php);
void HPPop(HP* php);
bool HPEmpty(HP* php);
void Adjustdown(HPTypeDate* a, HPTypeDate n,HPTypeDate parent);

堆常用的函數，初始化，插入，上下調整，取堆頂元素，消堆頂元素

函數解釋

void HeapInit(HP* php)
{assert(php);php->a = (HPTypeDate*)malloc(sizeof(HPTypeDate) * 4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}

初始化，為數組a開辟空間，size賦值，capacity先賦值4，

void HeapPrint(HP* php, HPTypeDate n)
{assert(php);for (int i = 0;i < n;i++){printf("%d ", php->a[i]);}printf("\n");
}
void swap(HPTypeDate* a, HPTypeDate* b)
{int p = *b;*b = *a;*a = p;
}

打印和交換函數

void Adjustup(HPTypeDate* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}

向上調整函數，非常重要，傳入child，是某個節點的下標。再找出父親節點，判斷孩子和父親節點的大小，根據建大小堆的不同 if中判斷符號作改變，我這里是小堆，再遞歸，父親的位置給孩子，父親根據公式 再重新向上找點，一直往復，直到不滿足堆的規定時間復雜度為O(log n）；

void Adjustdown(HPTypeDate* a,HPTypeDate n, HPTypeDate parent)
{HPTypeDate child = parent * 2+1;while (child < n){if (child+1<n&&a[child] < a[child + 1]){child = child + 1;}if (a[parent] > a[child]){swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else break;}
}

向下調整，傳入父節點下標，求出孩子結點，找出那個大孩子，再根據大小堆是否與孩子交換，遞歸，與向上類似時間復雜度與向上一致

void HeapPush(HP* php, HPTypeDate x)
{assert(php);if (php->capacity == php->size){HPTypeDate* tmp = (HPTypeDate*)realloc(php->a, sizeof(HPTypeDate) * (php->capacity) * 2);if (tmp == NULL){perror("realloc");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size++] = x;Adjustup(php->a, php->size - 1);
}

插入函數，判斷空間夠不夠，不夠realloc再開辟capacity2的，把開辟的空間給a，capacity=2；
將新來的數插入數組末尾，再向上調整一遍。時間復雜度最壞O(n),均攤O(1)

bool HPEmpty(HP* php)
{return php->size == 0;
}
HPTypeDate HPTop(HP* php)
{assert(php);return php->a[0];
}
void HPPop(HP* php)
{assert(php);if (HPEmpty(php)) return;swap(&php->a[0], &php->a[php->size - 1]);php->size--;Adjustdown(php->a, php->size,0);
}

消去堆頂函數，將堆頂和堆尾交換，size-- 就行，再將堆頂向下調整

堆排序O(n logn)

#include <stdio.h>void swap(int* a, int* b)
{int p = *a;*a = *b;*b = p;
}
void Adjustdown(int* a, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1])child = child + 1;if (a[child] > a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else break;}}
void heap_sort(int* a, int n)
{for (int i = (n - 2) / 2;i >= 0;i--){Adjustdown(a, i, n);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);Adjustdown(a, 0, end);end--;}
}
int main()
{int a[] = { 1,9,8,5,6,4,7,4 };heap_sort(a, 8);for (int i = 0;i < 8;i++){printf("%d ", a[i]);}return 0;
}

先前向上調整函數參數為指針，可以直接用來排序，
先將數組建成一個大堆，從中間開始往下調整O(n)，但從下向上調整O(nlogn)
默認升序，若想降序

• 方法 1：改用 小根堆（最小堆），這樣堆頂是最小值，交換到末尾后自然形成降序。

• 方法 2：仍然用 大根堆，但 不交換堆頂到末尾，而是 直接輸出堆頂（每次取最大值），但這樣會破壞原數組

topk問題

給出一堆數讓求最大的前k個，若給幾十億個數，開辟不了這么大的內存，所以要取巧，
建k個大小的小堆，遍歷一遍數，若比堆頂大就代替堆頂，進堆，最后幾個就是最大的

#include <stdio.h>void swap(int* a, int* b)
{int p = *a;*a = *b;*b = p;
}
void Adjustdown(int* a, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1])child = child + 1;if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else break;}}
void heap_sort(int* a, int k)
{//建堆for (int i = (k - 2) / 2;i >= 0;i--){Adjustdown(a, i, k);}//n-k比較for(int i=k;i<8;i++){int val = a[i];if (val > a[0]){swap(&val, &a[0]);Adjustdown(a, 0, k);}}
}
int main()
{int a[] = { 1,9,8,5,6,4,7,4 };int k = 2;heap_sort(a, k);for (int i = 0;i < k;i++){printf("%d ", a[i]);}return 0;
}

代碼稍微一改就行，要求前k小的就建大堆，若比堆頂小，代替進堆