目錄
一、堆的概念及結構
二、小根堆的實現
2.1 堆的數據結構
2.2 堆的初始化HeapInit
2.3 堆的銷毀HeapDestory
2.4 堆的插入HeapPush
?2.4.1 插入代碼HeapPush
2.4.2 向上調整代碼AdjustUp
2.4.3 交換數據代碼Swap
2.5 堆的刪除HeapPop
2.5.1 刪除代碼HeapPop
2.5.2 向下調整算法AdjustDown
2.6?取堆頂的數據HeapTop
2.7?獲取堆的數據個數HeapSize
2.8?堆的判空HeapEmpty
三、堆的應用
3.1 堆排序
3.2 TOP-K問題
3.2.1 創建大量數據
3.2.2 求K個最大的元素
3.2.3 驗證
四、代碼
4.1 堆的代碼
4.1.1 Heap.h
4.1.2 Heap.c
4.2 堆排序的代碼
4.3 TOP-K的代碼
一、堆的概念及結構
堆(Heap)是一種特殊的數據結構,通常以完全二叉樹的形式呈現。
堆的核心特性是:
- 對于大根堆,任意父節點的值都大于或等于其子節點的值
- 對于小根堆,任意父節點的值都小于或等于其子節點的值
堆通常使用數組來模擬完全二叉樹的結構。數組索引按照從上到下、從左到右的方式對應樹的節點排列。假設某個節點在數組中的位置為i
,則其左子節點和右子節點的位置分別為 2*i+1
和 2*i+2
,而其父節點的位置為(i-1)/2
。
如下所示:
二、小根堆的實現
2.1 堆的數據結構
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
2.2 堆的初始化HeapInit
void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}
2.3 堆的銷毀HeapDestory
// 堆的銷毀
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}
2.4 堆的插入HeapPush
假如,我們現在有一個數組a:15 18 19 25 28 34 65 49 27 37,他從邏輯上看,是一個小根堆結構,我們將它的邏輯結構畫出來如下所示:
我們現在想要將10插入堆里面去,插入10之后,要不允許破壞原本小根堆的結構,所以我們就需要將10一步一步的調整,如下所示:
2.4.1 插入代碼HeapPush
// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
2.4.2 向上調整代碼AdjustUp
//向上調整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
2.4.3 交換數據代碼Swap
//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
2.5 堆的刪除HeapPop
堆的刪除,我們首先要確定刪除哪一個元素,看上面的數組a:10 15 19 25 18 34 65 49 27 37 28.我們畫出他的二叉樹表現形式,如下所示,他滿足小根堆特性。
?現在數組中有這么多的元素,我們要刪除哪一個呢?最常見的是刪除第一個元素和最后一個元素,如果我們刪除最后一個元素28,刪除的沒有意義,他既不是最大的也不是最小的,所以堆的刪除一般都是刪除堆頂元素,也就是以一個元素,刪除堆頂元素之后,后面的元素需要向前移動嗎?答案是不能,如果向前移動,元素之間的邏輯關系會改變,不滿足小堆特性,所有如果我們要刪除第一個元素,通常做法是將最后一個元素與第一個元素互換,只有第一個元素不滿足小根堆的特性,其他元素都滿足,我們還需要寫一個向下調整算法。
2.5.1 刪除代碼HeapPop
// 堆的刪除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}
2.5.2 向下調整算法AdjustDown
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
2.6?取堆頂的數據HeapTop
// 取堆頂的數據
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}
2.7?獲取堆的數據個數HeapSize
// 堆的數據個數
int HeapSize(Heap* php) {assert(php);return php->size;
}
2.8?堆的判空HeapEmpty
// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}
三、堆的應用
3.1 堆排序
如果我們想要升序的話,就需要建立大根堆。
如果我們想要降序的話,就需要建立小根堆。
現在我們有一個數組a{ 27,15,19,18,28,34,65,49,25,37 };我們想要將a進行從小到大排序,所以我們就需要對這個數組進行建堆處理。
那現在我們如何建堆呢?
方法一:我們可以訪問數組的每一個元素,然后初始化一個堆,將數組的每一個元素插入到堆里面,我們根據堆的自動調整算法,可以自動的變成大根堆,然后我們取出堆頂的元素,把它放在數組里面,然后堆的刪除,重復n次。但是這樣空間復雜度太高了需要重新新建一個堆。
方法二:我們可以從數組的第二個元素開始,進行向上調整算法,就這個數組變成一個堆,如下所示:
for (int i = 1; i < size; i++) {AdjustUp(a, i);
}
我們打開我們的調試,看到數組a成功的變成了一個大根堆。但是這樣時間復雜度太高了。
方法三:可以從最后一個分支節點開始,依次進行向下調整算法,如下所示:
for (int i =(size-2)/2 ; i >= 0; i--)//
{AdjustDown(a, i, size);
}
我們常用的建堆算法是方法三。?
建完堆之后,我們將堆頂元素與最后一個元素互換,然后重新調整堆,重復n次。代碼如下所示:
int end = size - 1;
while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;
}
這樣我們就成功的將數組a從小到大排序了。
3.2 TOP-K問題
TOP-K問題:即求數據結合中前K個最大的元素或者最小的元素,一般情況下數據量都比較大。
比如:專業前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題,能想到的最簡單直接的方式就是排序,但是:如果數據量非常大,排序就不太可取了(可能數據都不能一下子全部加載到內存中)。最佳的方式就是用堆來解決,基本思路如下:
1. 用數據集合中前K個元素來建堆
????????前k個最大的元素,則建小堆
????????前k個最小的元素,則建大堆
2. 用剩余的N-K個元素依次與堆頂元素來比較,不滿足則替換堆頂元素
????????將剩余N-K個元素依次與堆頂元素比完之后,堆中剩余的K個元素就是所求的前K個最小或者最大的元素。
3.2.1 創建大量數據
我們使用代碼創建大量的數據,如下所示:
void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = rand()+i;fprintf(pf, "%d\n", number);}
}
3.2.2 求K個最大的元素
首先,輸入k的值,malloc出k個int類型的空間,然后從文件中讀取前k個數,將他們放在malloc出來的空間里面,將他們建成小堆,最后依次讀取文件中后n-k個,依次與堆頂進行比較,如果大于堆頂就替換,然后調整堆。代碼如下:
void TOP_K() {printf("請輸入k:");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//從文件中拷貝k個數到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k個數的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//讀取剩下的n-k個數據int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d個數", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}
3.2.3 驗證
我們現在已經把最大的前k個輸出了,我們如何驗證這k個元素就是十萬個數據中最大的前10個呢?
我們在創建數據的時候可以%10000000,來控制我們的數據,創建完成數據之后,我們在data.txt文檔中隨機的修改k個數,在它們后面加上4個0,這樣我們就知道k個最大的數后面肯定有4個0。我們調用top-k函數,如下所示:
四、代碼
4.1 堆的代碼
4.1.1 Heap.h
#pragma once
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
void AdjustDown(HPDataType* a, int parent, int size);
void AdjustUp(HPDataType* a, int child);
//交換函數
void Swap(HPDataType* x, HPDataType* y);
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);
4.1.2 Heap.c
#include"Heap.h"
void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}
// 堆的銷毀
void HeapDestory(Heap* php) {assert(php);free(php->a);php->capacity = php->size = 0;
}
//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上調整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->capacity == php->size) {int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("HeapPush()::realloc");exit(1);}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
// 堆的刪除
void HeapPop(Heap* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, 0, php->size);
}
// 取堆頂的數據
HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}
// 堆的數據個數
int HeapSize(Heap* php) {assert(php);return php->size;
}
// 堆的判空
int HeapEmpty(Heap* php) {return php->size == 0 ? 1 : 0;
}
4.2 堆排序的代碼
//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
//向上調整,建立大根堆
void AdjustUp(HPDataType* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}child = parent;parent = (child - 1) / 2;}
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] > a[child]) {child++;}if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void HeapSort(int* a, int size) {for (int i =(size-2)/2 ; i >= 0; i--)//{AdjustDown(a, i, size);}int end = size - 1;while (end > 0) {Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;}
}
int main() {int a[] = { 27,15,19,18,28,34,65,49,25,37 };int size = sizeof(a) / sizeof(a[1]);HeapSort(a, size);for (int i = 0; i < size; i++) {printf("%d ", a[i]);}return 0;
}
4.3 TOP-K的代碼
//交換函數
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(HPDataType* a, int parent, int size) {int child = 2 * parent + 1;while (child < size) {if (child + 1 < size && a[child + 1] < a[child]) {child++;}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);}parent = child;child = 2 * parent + 1;}
}
void CreatData() {FILE* pf = fopen("data.txt", "w");if (pf == NULL) {perror("fopen");exit(1);}int num = 100000;for (int i = 0; i < num; i++) {int number = (rand()+i)%10000000;fprintf(pf, "%d\n", number);}
}
void TOP_K() {printf("請輸入k:");int k = 0;scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL) {perror("malloc fail");exit(1);}//從文件中拷貝k個數到堆里面FILE* pf = fopen("data.txt", "r");if (pf == NULL) {perror("fopen");exit(1);}for (int i = 0; i < k; i++) {fscanf(pf, "%d", &kminheap[i]);}//建立k個數的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(kminheap, i, k);}//讀取剩下的n-k個數據int x = 0;while (fscanf(pf,"%d", &x)>0) {if (x > kminheap[0]) {kminheap[0] = x;AdjustDown(kminheap, 0, k);}}printf("最大的前%d個數", k);for (int i = 0; i < k; i++) {printf("%d ", kminheap[i]);}printf("\n");
}
int main() {srand((unsigned int)time(NULL));CreatData();TOP_K();return 0;
}