一、堆的初步認識

堆雖然是用數組存儲數據的數據結構，但是它的底層卻是另一種表現形式。

堆分為大堆和小堆，大堆是所有父親大于孩子，小堆是所有孩子大于父親。

?通過分析我們能得出父子關系的計算公式，parent=(child-1)/2，左孩子leftchild=parent*2+1，右孩子rightchild=parent*2+2，這會在下面實現時應用。

二、堆實現

1、頭文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapPrint(HP* php);//堆打印
void HeapInit(HP* php);//堆初始化
void HeapPush(HP* php, HPDataType x);//堆插入
void HeapPop(HP* php);//堆刪除
HPDataType HeapTop(HP* php);//返回堆頂元素
bool HeapEmpty(HP* php);//判空
int HeapSize(HP* php);//返回堆大小
void AdjustUp(HPDataType* a, int child);//向上調整
void AdjustDown(HPDataType* a, int n, int parent);//向下調整
void Swap(HPDataType* x, HPDataType* y);//交換函數
void HeapSort(int* arr, int n);//堆排序
void HeadDestroy(HP* php);//堆銷毀

這里用結構體管理數據，HPDataType*a是動態數組的指針，HPDataType是typedef定義的可變參數，需要更改存儲類型時，修改typedef的內容即可，size用于統計存儲數據的多少，capacity是統計開辟的空間大小，即動態申請數組的大小。?

2、 堆初始化

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

assert檢查指針是否為空，malloc動態申請空間，然后對size和capacity(空間的大小)初始化?

3、堆打印

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

?4、向上調整

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;/*while (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}*/while (child > 0) //與下面風格相同{if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else break;}
}

向上調整用于解決插入數據造成的不構成堆的問題?

5、堆插入

當我們插入一個值時，這個新插入的值也許會破壞原本的堆關系，所以我們需要進行向上調整，使其恢復堆關系。?

void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* php->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;//size代表元素個數，a[size]為下一個元素php->size++;AdjustUp(php->a, php->size - 1);//向上調整
}

?6、向下調整

void AdjustDown(HPDataType* a,int n ,int parent)
{/*int child = a[parent * 2 + 1] > a[parent * 2 + 2] ? parent * 2 + 1 : parent * 2 + 2;while (child < n){Swap(&a[parent], &a[child]);parent = child;child = a[parent * 2 + 1] > a[parent * 2 + 2] ? parent * 2 + 1 : parent * 2 + 2;}*/int child = parent * 2 + 1;//左孩子while (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;}
}

7、堆刪除

這里選擇堆頂元素和堆底元素交換，如果挪動數據會導致父子關系亂套，而這里不free最后一個元素，避免釋放后繼續使用。

void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));//挪動刪除:1.效率低下2.關系全亂//只需要交換第一個元素和最后一個元素值，并php->size--//1.效率高2.保持父子關系Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);}

?8、返回堆頂元素

HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}

動態數組中存儲的第一個元素就是堆頂元素??

9、堆判空

bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

通過size的數量判空，如果為0，則堆為空，返回true?

?10、堆大小

int HeapSize(HP* php)
{assert(php);return php->size;
}

?這里結構體中有size數據，返回即可。

11、堆銷毀

void HeadDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

?free掉a指針指向的空間，a指針置空，size和capacity賦值0.

三、擴展

1、堆排序(升序大堆，降序小堆)

時間復雜度O(N*logN)

先對要排序的數組建堆，然后交換堆頂元素，對剩余的元素向下調整。

void HeapSort(int* arr, int n)
{for (int i = (n-2)/2; i >0; i--){AdjustDown(arr, n, i);}int end = n - 1;while (end){Swap(&arr[0], &arr[end]);AdjustDown(arr, end, 0);end--;}
}

2、topk問題

?用k個元素建小堆，剩余n-k個元素與堆頂元素比較交換即可，最后k大小的小堆中保留的是這n個數中前k個最大的數。

看到最后，如果對您有所幫助，請點贊、收藏和關注，點點關注不迷路，源碼已上傳Gitee有需自取：白天沒有黑夜 (not-during-the-day) - Gitee.com，我們下期再見！