//取堆頂?shù)脑?HDataType HeapTop(Heap* php);

將該函數(shù)命名為HeapTop，函數(shù)的參數(shù)是結(jié)構(gòu)體指針，函數(shù)的返回值是堆跟結(jié)點內(nèi)的數(shù)據(jù)

在完成了函數(shù)的聲明后就是在Heap.c內(nèi)完成函數(shù)的定義

//取堆頂?shù)脑?HDataType HeapTop(Heap* php)
{assert(php);return php->arr[0];
}

6.堆的數(shù)據(jù)個數(shù)?

在求堆的數(shù)據(jù)個數(shù)函數(shù)的實現(xiàn)中先要在Heap.h內(nèi)完成堆的數(shù)據(jù)個數(shù)函數(shù)的聲明

//堆的數(shù)據(jù)個數(shù)
int HeapSize(Heap* php);

將該函數(shù)命名為HeapSize，函數(shù)的參數(shù)是結(jié)構(gòu)體指針，函數(shù)的返回值是堆的結(jié)點結(jié)點個數(shù)

在完成了函數(shù)的聲明后就是在Heap.c內(nèi)完成函數(shù)的定義
因為堆是用數(shù)組來實現(xiàn)的，所以堆中的結(jié)點個數(shù)就為數(shù)組的有效元素個數(shù)

//堆的數(shù)據(jù)個數(shù)
int HeapSize(Heap* php)
{assert(php);return php->size;
}

7.堆的判空

在判斷堆是否為空函數(shù)的實現(xiàn)中先要在Heap.h內(nèi)完成判斷堆是否為空函數(shù)的聲明

//堆的判空
bool HeapEmpty(Heap* php);

將該函數(shù)命名為HeapEmpty，函數(shù)的參數(shù)是結(jié)構(gòu)體指針，函數(shù)的返回類型是布爾類型

在完成了函數(shù)的聲明后就是在Heap.c內(nèi)完成函數(shù)的定義
在該函數(shù)中當當堆為空時就返回true，不為空時返回false

//堆的判空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

8.堆的銷毀

在堆的銷毀函數(shù)的實現(xiàn)中先要在Heap.h內(nèi)完成堆的銷毀函數(shù)的聲明

//銷毀堆
void HeapDestory(Heap* php);

將該函數(shù)命名為HeapDestory，函數(shù)的參數(shù)是結(jié)構(gòu)體指針

在完成了函數(shù)的聲明后就是在Heap.c內(nèi)完成函數(shù)的定義

//銷毀堆
void HeapDestory(Heap* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->size = php->capacity = 0;
}

?9.堆實現(xiàn)完整代碼

Heap.h

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆結(jié)構(gòu)的定義
typedef int HDataType;
typedef struct Heap
{HDataType* arr;int size;//有效數(shù)據(jù)個數(shù)int capacity;//空間大小
}Heap;//初始化堆
void HeapInit(Heap* php);
//銷毀堆
void HeapDestory(Heap* php);
//堆的插入
void HeapPush(Heap* php,HDataType x);
//堆的刪除
void HeapPop(Heap* php);
//取堆頂?shù)脑?HDataType HeapTop(Heap* php);
//堆的數(shù)據(jù)個數(shù)
int HeapSize(Heap* php);
//堆的判空
bool HeapEmpty(Heap* php);
//向上調(diào)整法
void AdjustUp(HDataType* arr, int child);
//向下調(diào)整法
void AdjustDown(HDataType* arr, int n, int parent);

Heap.c

#include"Heap.h"void Swap(HDataType* p1, HDataType* p2)
{HDataType* tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上調(diào)整法
void AdjustUp(HDataType* arr, int child)
{int parent = (child - 1) / 2;while (child>0){//小堆 <//大堆 >if (arr[child] < arr[parent]){Swap(&arr[child], & arr[parent]);child = parent;parent= (child - 1) / 2;}else{break;}}}//向下調(diào)整法
void AdjustDown(HDataType* arr, int n, int parent)
{int child = 2 * parent + 1;while (child<n){//小堆 >//大堆 <if (child+1<n && arr[child] > arr[child + 1]){child++;}if (arr[parent] > arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child= 2 * parent + 1;}else{break;}}
}//初始化堆
void HeapInit(Heap* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}//銷毀堆
void HeapDestory(Heap* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->size = php->capacity = 0;
}//堆的插入
void HeapPush(Heap* php, HDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;Heap* tmp = (Heap*)realloc(php->arr,sizeof(HDataType) * newcapacity);if (tmp == NULL){perror("malloc file");exit(1);}php->arr = tmp;php->capacity = newcapacity;}php->arr[php->size] = x;AdjustUp(php->arr, php->size);php->size++;
}//堆的刪除
void HeapPop(Heap* php)
{assert(php && php->size);php->arr[0] = php->arr[php->size - 1];--php->size;AdjustDown(php->arr, php->size, 0);
}//取堆頂?shù)脑?HDataType HeapTop(Heap* php)
{assert(php);return php->arr[0];
}//堆的數(shù)據(jù)個數(shù)
int HeapSize(Heap* php)
{assert(php);return php->size;
}//堆的判空
bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

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

1.堆排序

在之前的C語言的學(xué)習(xí)當中我們實現(xiàn)了冒泡排序，但在算法的復(fù)雜度中得出了冒泡排序的時間復(fù)雜度為O(n^2),因此其實冒泡排序的效率是不高的。接下來我們就要來學(xué)習(xí)一種使用堆來實現(xiàn)排序的算法。

在此之前通過學(xué)習(xí)堆的相關(guān)概念知道了在小堆中的根結(jié)點是堆中最小的，那么在小堆中只要一直取堆的根結(jié)點就可以得到升序的數(shù)據(jù)，以下就是使用這種方法來實現(xiàn)的堆排序

void HeapSort(int* a, int n)
{Heap hp;for(int i = 0; i < n; i++){HeapPush(&hp,a[i]);}int i = 0;while (!HeapEmpty(&hp)){a[i++] = HeapTop(&hp);HeapPop(&hp);}HeapDestroy(&hp);
}

但是在以上的這種算法中需要將數(shù)組中的數(shù)據(jù)先要先存儲在堆當中才能在之后得到堆頂?shù)臄?shù)據(jù)，因此以上這種方法的空間復(fù)雜度就為O(n),那么有什么方法能在不申請新的空間下來實現(xiàn)堆排序呢？接下來就來看以下的這種基于原來數(shù)組建堆的方法

//堆排序算法
void HeapSort(int* arr, int n)
{for (int i = 0; i < n; i++){AdjustUp(arr, i);}int end = n - 1;while (end > 0){Swap(&arr[end], &arr[0]);AdjustDown(arr, end, 0);end--;}for (int i = 0; i < n; i++){printf("%d ", arr[i]);}
}

在以上這種堆排序中先用向上調(diào)整法來將數(shù)組通過循環(huán)的將數(shù)組數(shù)組調(diào)整為堆，根據(jù)之前向上調(diào)整的代碼在此的建的是小堆。之后的while循環(huán)中實現(xiàn)的是將小堆中的跟結(jié)點和尾結(jié)點進行交換這時數(shù)組中最小的元素就排在了數(shù)組的末尾之后再進行向下排序就可重新變?yōu)樾《?#xff0c;一直重復(fù)以上的操作就可以將數(shù)組的元素從小到大依次移動到數(shù)組末尾，最終原數(shù)組就變?yōu)樯虻牧恕?/span>

那么以上除了使用向上調(diào)整建堆外，其實使用向下調(diào)整法也可以建堆，以下是使用向下調(diào)整法建堆的代碼

//堆排序算法
void HeapSort(int* arr, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, n, i);}int end = n - 1;while (end > 0){Swap(&arr[end], &arr[0]);AdjustDown(arr, end, 0);end--;}for (int i = 0; i < n; i++){printf("%d ", arr[i]);}
}

這兩種那一這種效率更好呢，這就需要來分析向上建堆和向下建堆的時間復(fù)雜度

先來看向上調(diào)整法

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復(fù)雜度本來看的就是近似值，多幾個結(jié)點不影響最終結(jié)果)

以下是各層的結(jié)點在向上調(diào)整過程中各層結(jié)點在調(diào)整過程中最壞的情況下移動的層數(shù)

需要移動結(jié)點總的移動步數(shù)為：每層結(jié)點個數(shù) * 向上調(diào)整次數(shù)（第?層調(diào)整次數(shù)為0）

由此可得：
💡 向上調(diào)整算法建堆時間復(fù)雜度為： O(n ? log2 n)

接下來看向下調(diào)整法

以下是各層的結(jié)點在向下調(diào)整過程中各層結(jié)點在調(diào)整過程中最壞的情況下移動的層數(shù)

則需要移動結(jié)點總的移動步數(shù)為：每層結(jié)點個數(shù) * 向下調(diào)整次數(shù)?

💡 向下調(diào)整算法建堆時間復(fù)雜度為： O(n)?

通過以上的分析后可以得出在堆排序中使用向下調(diào)整法建堆更好

堆排序第二個循環(huán)中的向下調(diào)整與建堆中的向上調(diào)整算法時間復(fù)雜度計算一致。因此堆排序的時間復(fù)雜度為 O(n + n ? log n) ，即 O(n log n)

?

?

2.TOP-K問題

TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下?全部加載到內(nèi)存中)。最佳的方式就是用堆來解決，基本思路如下：

（1）用數(shù)據(jù)集合中前K個元素來建堆
? ? ? 前k個最大的元素，則建小堆
? ? ? 前k個最小的元素，則建大堆
（2）用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素
將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者大的元素

以下這段代碼可以實現(xiàn)將大量的整型數(shù)據(jù)輸入到data.txt的文件當中

void CreateNDate()
{// 造數(shù)據(jù)int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}

?接下來就來實現(xiàn)解決TOP-K問題的代碼，以下是實現(xiàn)的是得出數(shù)據(jù)結(jié)合中前K個最大的元素

void topk()
{int k=0;printf("k:");scanf("%d", &k);//讀取文件中的前k個數(shù)據(jù)FILE* pf = fopen("data.txt", "r");if (pf == NULL){perror("fopen fail");exit(1);}int* pa = (int*)malloc(k * sizeof(int));if (pa == NULL){perror("malloc fail");exit(2);}for (int i = 0; i < k; i++){fscanf(pf, "%d", &pa[i]);}//使用前k個數(shù)據(jù)建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(pa, k, i);}int tmp=0;//循環(huán)將k個數(shù)據(jù)之后的數(shù)據(jù)堆中最小的元素比較，若比這個元素大就交換while (fscanf(pf, "%d", &tmp) != EOF){if (tmp > pa[0]){pa[0] = tmp;AdjustDown(pa, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", pa[i]);}fclose(pf);pf = NULL;}

?

?

以上就是二叉樹(中)的全部內(nèi)容了，接下來在二叉樹(下)將繼續(xù)學(xué)習(xí)二叉樹的知識，在下一篇中我們將重點學(xué)習(xí)鏈式結(jié)構(gòu)的二叉樹的相關(guān)知識，未完待續(xù)……?