目錄

1.堆的概念

2.堆的構(gòu)建

3.堆的實(shí)現(xiàn)

4.堆的功能實(shí)現(xiàn)

4.1堆的初始化

4.2堆的銷毀

4.3堆的插入

4.3.1向上調(diào)整

4.4堆的刪除

4.4.1向下調(diào)整法

?編輯4.5取堆頂

5. 向上調(diào)整法和向下調(diào)整法比較

?6.堆的應(yīng)用

6.1TOP-K問(wèn)題

6.2TOP-K思路

6.2.1用前n個(gè)數(shù)據(jù)來(lái)建堆

6.2.2剩下的N-K?

6.3示例

---

1.堆的概念

堆的底層是數(shù)組，所以堆也是一種特殊的數(shù)組。

堆分為大堆和小堆

• 大堆：父節(jié)點(diǎn)不小于子節(jié)點(diǎn)
• 小堆：父節(jié)點(diǎn)不大于子節(jié)點(diǎn)

2.堆的構(gòu)建

已經(jīng)提到堆是一種數(shù)組，那么要怎么實(shí)現(xiàn)呢。

先以小堆為例，已知父節(jié)點(diǎn)不小于子節(jié)點(diǎn)，使用數(shù)組，數(shù)組下標(biāo)0是根節(jié)點(diǎn)，1和2是他的子節(jié)點(diǎn)，接著1的子節(jié)點(diǎn)是3和4,2的子節(jié)點(diǎn)是5和6，這樣就可以實(shí)現(xiàn)一個(gè)堆了。

3.堆的實(shí)現(xiàn)

既然是數(shù)組，就要有指針，容量大小。

4.堆的功能實(shí)現(xiàn)

4.1堆的初始化

4.2堆的銷毀

4.3堆的插入

一直到這一步，都是和棧是相同的，因?yàn)槲覀儾迦霐?shù)據(jù)了，這時(shí)我們無(wú)法保證這是一個(gè)堆，所以此時(shí)要進(jìn)行向上調(diào)整。

4.3.1向上調(diào)整

因?yàn)榇藭r(shí)插入是數(shù)據(jù)再最下面，所以要和上面的進(jìn)行比較調(diào)整。

4.4堆的刪除

我們是刪除堆的最后一個(gè)元素，要怎么刪除呢，我們可以將最后一個(gè)元素和第一個(gè)元素進(jìn)行交換，然后使堆向下調(diào)整即可。

????????

4.4.1向下調(diào)整法

4.5取堆頂

5. 向上調(diào)整法和向下調(diào)整法比較

推導(dǎo)時(shí)間復(fù)雜度，由于用圖來(lái)表示有些難度，這里直接用筆寫出來(lái)

這是向下調(diào)整法的推導(dǎo)過(guò)程

向下調(diào)整建堆的時(shí)間復(fù)雜度如圖

下面是向上調(diào)整建堆的時(shí)間復(fù)雜度推導(dǎo)

總結(jié):向上調(diào)整算法建堆是優(yōu)于向下調(diào)整建堆的。

?6.堆的應(yīng)用

6.1TOP-K問(wèn)題

這種問(wèn)題通常是在較大的數(shù)據(jù)樣本中取出其中的最值，這時(shí)就可以通過(guò)堆來(lái)完成。

通常這類問(wèn)題樣本較大，排序就不太可取，可以建堆來(lái)實(shí)現(xiàn)。

6.2TOP-K思路

6.2.1用前n個(gè)數(shù)據(jù)來(lái)建堆

求最大的前n個(gè)就建小堆

求最小的前n個(gè)就建大堆

6.2.2剩下的N-K?

用剩下的N-K個(gè)數(shù)據(jù)來(lái)和堆頂數(shù)據(jù)比較，不滿足就替換堆頂元素

6.3示例

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
#include<time.h>
void test()
{HP hp;HPInit(&hp);HPPush(&hp, 2);HPPush(&hp, 4);HPPush(&hp, 1);HPPush(&hp, 1); printf("%d", HPTop(&hp));}
void CreateNDate()
{int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (file == NULL){perror("fopen fail");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void topk()
{int k = 0;printf("輸入k的值\n");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");int* arr = (int*)malloc(sizeof(int) * k);for (int i = 0; i < k; i++){fscanf(fout, "%d", &arr[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, k);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > arr[0]){arr[0] = x;AdjustDown(arr, 0, k);}}for (int i = 0; i < k; i++) {printf("%d ", arr[i]);}fclose(fout);
}int main()
{CreateNDate();topk();return 0;
}