C語言堆實現(xiàn)建堆算法和堆排序
一.什么是堆？
1.堆
堆就是完全二叉樹，而且是一種特殊的完全二叉樹，它需要滿足每一個父節(jié)點都大于子節(jié)點，稱為大堆，或每一個父節(jié)點都小于子節(jié)點，稱為小堆。而對兄弟節(jié)點之間的大小關系并沒有要求(為此它并不是有序的)。如下：
2.堆的儲存
對于完全二叉樹有一個更好的儲存方法，就是用順序表來儲存，相比鏈式儲存使用順序表儲存的一個很大的好處在于知道一個結點可以很容易的算出它父結點和子結點的下標，還有可以隨機訪問。
父子結點下標計算公式 ：
- 左子結點下標 = 父結點下標*2+1
- 右子結點下標 = 父結點下標*2+2
- 父結點下標 = (子結點下標-1) / 2
二.堆結構的創(chuàng)建
1.頭文件的聲明：
Heap.h
#pragma
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define HpDataType int
typedef int HPDataType;
typedef struct Heap
{
HPDataType* arr;
int size;
int cap;
}Heap;
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);//堆的判空
void AdjustUP(HpDataType* arr, int child);//向上調整
void AdjustDOWN(HpDataType* arr, int size, int parent);//向下調整
void Swap(HpDataType* a, HpDataType* b);//元素的交換其中堆的初始化，堆的銷毀，堆的數據個數，堆的判空，和取堆頂數據和順序表的操作是一樣的這里重點來學一下堆的插入，堆的刪除。
2.向上調整
插入元素呢直接往數組最后插入就可以，但是插入后就不一定是堆結構的，所以需要調整。例如一個大堆：
向大堆中插入53
調整后：
代碼示例：
void AdjustUP(HpDataType* arr,int child)
{
int parent = (child - 1) / 2;//計算父節(jié)點下標
while (child>0)//注意這里不能是parent>0
{
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);//封裝一個函數進行交換
child = parent;//更新子節(jié)點
parent = (child - 1) / 2;//更新父節(jié)點
}
else
break;
}
}★如果是小堆只需要把if條件的大于號改為小于號
3.向下調整
要注意刪除元素我們刪除的不是尾元素，這樣毫無意義，我們刪除的是下標為0位置的元素，它是整個堆中最小或最大的元素。怎么刪除呢？直接將它刪除然后后面的元素在覆蓋上嗎？這樣做的話，它就不是堆了，而且元素之間關系將會全部混亂，就需要從0開始創(chuàng)建堆，效率非常低，我們可以把首元素與尾元素互換然后刪除尾元素，雖然這個操作過后它也可能就不是堆了，不過我們可以將首元素向下調整，讓它成為堆。比剛才的方案效率要高得多。
比如我們刪除大堆中的一個元素
調整過程：
調整后的結果：
代碼示例：
void AdjustDOWN(HpDataType* arr, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if ((child+1)<size&&arr[child] < arr[child + 1])
child++;
if (arr[child] > arr[parent])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}★如果是小堆只需要把if條件里兄弟節(jié)點的大小關系和父子節(jié)點的大小關系改變一下就行
4.源碼：
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HeapInit(Heap* ps)//初始化
{
assert(ps);
ps->arr = NULL;
ps->cap = ps->size = 0;
}
void HeapDestory(Heap* hp)//銷毀堆
{
assert(hp);
free(hp->arr);
hp->cap = hp->size = 0;
}
void Swap(HpDataType* a, HpDataType* b)//交換元素
{
HpDataType c = *a;
*a = *b;
*b = c;
}
void AdjustUP(HpDataType* 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;
}
}
void AdjustDOWN(HpDataType* arr, int size, int parent)//向上調整
{
int child = parent * 2 + 1;
while (child < size)
{
if (arr[child] > arr[child + 1])
child++;
if ((child+1)<size&&arr[child] < arr[parent])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapPush(Heap* ps, HPDataType x)//插入元素
{
assert(ps);
if (ps->size == ps->cap)
{
int pnc = ps->cap == 0 ? 4 : 2 * ps->cap;
HpDataType* pnew = realloc(ps->arr, sizeof(HPDataType)*pnc);
assert(pnew);
ps->arr = pnew;
ps->cap = pnc;
}
ps->arr[ps->size] = x;
ps->size++;
AdjustUP(ps->arr, ps->size - 1);
}
void HeapPop(Heap* hp)//刪除元素
{
assert(hp);
assert(hp->size);
if (hp->size == 1)
{
hp->size--;
return;
}
Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
hp->size--;
AdjustDOWN(hp->arr, hp->size, 0);
}
HPDataType HeapTop(Heap* hp)//取堆頂元素
{
assert(hp);
assert(hp->size);
return hp->arr[0];
}
int HeapSize(Heap* hp)//計算堆元素個數
{
assert(hp);
return hp->size;
}
int HeapEmpty(Heap* hp)//判斷堆是否為空
{
assert(hp);
return hp->size == 0;
}三.建堆算法
在學習建堆算法的時候我們以對數組建堆為例，就是把數組的數據之間的關系做成一個堆結構，一般有兩種方法，向上調整建堆和向下調整建堆，具體怎么做我們來看下面。
1.向上建堆法
向上建堆法也就是通過向上調整建堆，我們拿到一個數組后可以把數組的首元素當做堆，第二個元素當做把新的元素插入堆，然后通過向上調整構成新的堆，以此類推下去把數組遍歷完后一個堆就建成了。時間復雜度為O(N*logN)
代碼示例：
#include<stdio.h>
#include"Heap.h"
int main()
{
int arr[] = { 1,9,3,7,6,4,2,10,8,5 };
int size = sizeof(arr) / sizeof(int);
for (int i = 0; i < size; i++)
AdjustUP(arr, i);//該函數在上文已給出，這里不再展示
printf("建大堆后：\n");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
return 0;
}不過該方法相比向下調整建堆效率比較低，我們來看向下調整建堆法。
2.向下建堆法
向下建堆法也就是通過向下調整建堆，要注意并不是從首元素開始調整，因為剛開始它并不滿足左右子樹都是堆結構，所以不能直接從第一個元素開始向下調整。既然要滿足左右子樹都是堆那么我們可以考慮從最后一個元素開始調整，不過最后一層下面已經沒有元素了，它已經是堆，并不用調整，那么我們從倒數第二層開始調整，所以我們先來計算一下倒數第二層最后一個父節(jié)點的下標：
(size-1-1)/2
第一個size-1得到二叉樹的最后一個元素的下標，再減一除以二得到它的父節(jié)點的下標。
代碼示例：
#include<stdio.h>
#include"Heap.h"
int main()
{
int arr[] = { 1,9,3,7,6,4,2,10,8,5 };
int size = sizeof(arr) / sizeof(int);
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
AdjustDOWN(arr, size,i);//該函數在上文已給出，這里不再展示
printf("建大堆后：\n");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
return 0;
}它的時間復雜度為O(N)證明如下：
其中Sn為總的調整次數.
四.堆排序
給一個數組建堆后利用堆的性質給數組排序，使其效率更高，這就是一個堆排序。比如現(xiàn)在要對一個數組進行堆排序，第一個問題就是建大堆還是小堆，怎么利用堆來給數組排序。
要進行升序就需要建大堆，如果建的是小堆，那么堆頂也就是首元素就是最小的元素，并不需要動，那么來處理第二個元素就注意到它并不一定是第二小的元素，只能從第二個元素開始重新建一個小堆，那么每排一個元素都需要重新建一個小堆效率就會變得很低。
升序建大堆的話，第一個元素就是最大的元素，我們可以讓它與最后一個元素互換，然后把堆的元素個數減一(就是把最后一個元素當做是堆外)，最后把堆頂元素向下調整，反復操作直到堆的元素個數變?yōu)榱肆?。這樣一個數組就按升序排好了。
降序需要建小堆，原理和排升序相同這里就不在贅述。
代碼示例：
#include<stdio.h>
#include"Heap.h"
int main()
{
int arr[] = { 1,9,3,7,6,4,2,10,8,5 };
int size = sizeof(arr) / sizeof(int);
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
AdjustDOWN(arr, size,i);
printf("建大堆后：\n");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
while (size)
{
Swap(&arr[0], &arr[size - 1]);//交換元素
size--;
AdjustDOWN(arr, size, 0);
}
printf("\n排序后；\n");
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
printf("%d ", arr[i]);
return 0;
}五.在文件中Top出最小的K個數
用堆結構的一個好處就在于，不需要排序就能高效的找出最小的前n個元素或最大的前n個元素，現(xiàn)在我們來利用堆來嘗試找出文件中最小的K個數，一個比較低效的一個方法就是把文件中涉及到的所以數據都取出來然后把它建成一個小堆，然后Pop出前k次，得到最小的k個數。但是如果這個數據非常的大呢，比如有上億個數據，那么就會消耗很大的內存空間。
有一個很優(yōu)的方法就是只取出文件的前K個數建成一個大堆，也就是說這個堆只用儲K個元素，那么堆頂就是這個堆的最大元素，然后繼續(xù)遍歷文件每遍歷一個元素都與堆頂元素作比較，如果比堆頂元素小就更新一下堆頂元素(把小的那個變成堆頂元素)，然后進行向下調整，直到遍歷完整個文件，那么此時堆中的元素就是文件中最小的K個元素。此方法在時間復雜度上與上一方法差不多，但它大大的節(jié)省了空間。
代碼示例：
#include<stdio.h>
#include"Heap.h"
void CreateNDate()
{
//造數據，寫入文件中
int n = 10000;
srand((unsigned int)time(NULL));
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() % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void PrintTopK(int k)
{
int* arr = (int*)malloc(sizeof(int) * k);
assert(arr);
FILE* fop = fopen("data.txt", "r");
if (!fop)
{
perror("fopen error");
return;
}
for (int i = 0; i < k; i++)//先取出k個建大堆
fscanf(fop, "%d", &arr[i]);
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
AdjustDOWN(arr, k, i);
int x = 0;
while (fscanf(fop, "%d", &x) != EOF)
{
if (arr[0] > x)
{
arr[0] = x;
AdjustDOWN(arr, k, 0);
}
}
for (int i = 0; i < k; i++)//輸出堆中元素
printf("%d ", arr[i]);
}
int main()
{
CreateNDate();
int k = 0;
scanf("%d", &k);
PrintTopK(k);
return 0;
}到此這篇關于C語言堆實現(xiàn)建堆算法和堆排序的文章就介紹到這了,更多相關C語言 堆 內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
在C++編程中,一個線程的棧內存通常是有限的,本文就來詳細介紹幾種避免棧溢出的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2025-09-09
Qt顯示QImage圖像在label上,并保持自適應大小問題
這篇文章主要介紹了Qt顯示QImage圖像在label上,并保持自適應大小問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章介紹了C語言找水仙花數最原始的笨方法，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-02-02
磁盤映射技術通過將文件映射到內存中,提高了文件操作的效率,本文就來介紹一下C語言實現(xiàn)磁盤映射,感興趣的可以了解一下2024-09-09
這篇文章主要介紹了C語言函數調用堆棧詳情分析，文章圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-07-07
在本篇文章里小編給大家整理了一篇關于C語言計算余數的圖文步驟內容，有需要的朋友們可以參考下。2020-02-02
這篇文章主要介紹了C++實現(xiàn)二叉樹遍歷序列的求解方法,需要的朋友可以參考下2014-08-08
這篇文章主要為大家介紹了C語言編程深入理解取整取余取模問題的示例分析詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2021-11-11
這篇文章主要介紹了如何配置國內鏡像源來使用vcpkg管理C++包,包括使用環(huán)境變量、修改配置文件、手動下載工具和使用預編譯二進制文件等方法,并提供了一個完整的解決方案和分步安裝策略,需要的朋友可以參考下2025-11-11
著先通過 HuffmanTree() 函數構造哈夫曼樹，然后在主函數 main()中自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷，若在父結點左側，則置碼為 0,若在右側,則置碼為 1。最后輸出生成的編碼2013-07-07