C語言堆實現(xiàn)建堆算法和堆排序

更新時間：2024年09月02日 09:28:09 作者：敲上癮

本文主要介紹了C語言堆實現(xiàn)建堆算法和堆排序,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

一.什么是堆？

1.堆

堆就是完全二叉樹，而且是一種特殊的完全二叉樹，它需要滿足每一個父節(jié)點都大于子節(jié)點，稱為大堆，或每一個父節(jié)點都小于子節(jié)點，稱為小堆。而對兄弟節(jié)點之間的大小關(guān)系并沒有要求(為此它并不是有序的)。如下：

2.堆的儲存

對于完全二叉樹有一個更好的儲存方法，就是用順序表來儲存，相比鏈式儲存使用順序表儲存的一個很大的好處在于知道一個結(jié)點可以很容易的算出它父結(jié)點和子結(jié)點的下標，還有可以隨機訪問。

父子結(jié)點下標計算公式：

左子結(jié)點下標 = 父結(jié)點下標*2+1
右子結(jié)點下標 = 父結(jié)點下標*2+2
父結(jié)點下標 = (子結(jié)點下標-1) / 2

二.堆結(jié)構(gòu)的創(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);//取堆頂?shù)臄?shù)據(jù)
int HeapSize(Heap* hp);//堆的數(shù)據(jù)個數(shù)
int HeapEmpty(Heap* hp);//堆的判空

void AdjustUP(HpDataType* arr, int child);//向上調(diào)整
void AdjustDOWN(HpDataType* arr, int size, int parent);//向下調(diào)整
void Swap(HpDataType* a, HpDataType* b);//元素的交換

其中堆的初始化，堆的銷毀，堆的數(shù)據(jù)個數(shù)，堆的判空，和取堆頂數(shù)據(jù)和順序表的操作是一樣的這里重點來學一下堆的插入，堆的刪除。

2.向上調(diào)整

插入元素呢直接往數(shù)組最后插入就可以，但是插入后就不一定是堆結(jié)構(gòu)的，所以需要調(diào)整。例如一個大堆：

向大堆中插入53

調(diào)整后：

代碼示例：

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]);//封裝一個函數(shù)進行交換
			child = parent;//更新子節(jié)點
			parent = (child - 1) / 2;//更新父節(jié)點
		}
		else
			break;
	}
}

★如果是小堆只需要把if條件的大于號改為小于號

3.向下調(diào)整

要注意刪除元素我們刪除的不是尾元素，這樣毫無意義，我們刪除的是下標為0位置的元素，它是整個堆中最小或最大的元素。怎么刪除呢？直接將它刪除然后后面的元素在覆蓋上嗎？這樣做的話，它就不是堆了，而且元素之間關(guān)系將會全部混亂，就需要從0開始創(chuàng)建堆，效率非常低，我們可以把首元素與尾元素互換然后刪除尾元素，雖然這個操作過后它也可能就不是堆了，不過我們可以將首元素向下調(diào)整，讓它成為堆。比剛才的方案效率要高得多。

比如我們刪除大堆中的一個元素

調(diào)整過程：

調(diào)整后的結(jié)果：

代碼示例：

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é)點的大小關(guān)系和父子節(jié)點的大小關(guān)系改變一下就行

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)//向下調(diào)整
{
	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)//向上調(diào)整
{
	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)//計算堆元素個數(shù)
{
	assert(hp);
	return hp->size;
}
int HeapEmpty(Heap* hp)//判斷堆是否為空
{
	assert(hp);
	return hp->size == 0;
}

三.建堆算法

在學習建堆算法的時候我們以對數(shù)組建堆為例，就是把數(shù)組的數(shù)據(jù)之間的關(guān)系做成一個堆結(jié)構(gòu)，一般有兩種方法，向上調(diào)整建堆和向下調(diào)整建堆，具體怎么做我們來看下面。

1.向上建堆法

向上建堆法也就是通過向上調(diào)整建堆，我們拿到一個數(shù)組后可以把數(shù)組的首元素當做堆，第二個元素當做把新的元素插入堆，然后通過向上調(diào)整構(gòu)成新的堆，以此類推下去把數(shù)組遍歷完后一個堆就建成了。時間復(fù)雜度為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);//該函數(shù)在上文已給出，這里不再展示
	printf("建大堆后：\n");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	return 0;
}

不過該方法相比向下調(diào)整建堆效率比較低，我們來看向下調(diào)整建堆法。

2.向下建堆法

向下建堆法也就是通過向下調(diào)整建堆，要注意并不是從首元素開始調(diào)整，因為剛開始它并不滿足左右子樹都是堆結(jié)構(gòu)，所以不能直接從第一個元素開始向下調(diào)整。既然要滿足左右子樹都是堆那么我們可以考慮從最后一個元素開始調(diào)整，不過最后一層下面已經(jīng)沒有元素了，它已經(jīng)是堆，并不用調(diào)整，那么我們從倒數(shù)第二層開始調(diào)整，所以我們先來計算一下倒數(shù)第二層最后一個父節(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);//該函數(shù)在上文已給出，這里不再展示
	printf("建大堆后：\n");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	return 0;
}

它的時間復(fù)雜度為O(N)證明如下：

其中Sn為總的調(diào)整次數(shù).

四.堆排序

給一個數(shù)組建堆后利用堆的性質(zhì)給數(shù)組排序，使其效率更高，這就是一個堆排序。比如現(xiàn)在要對一個數(shù)組進行堆排序，第一個問題就是建大堆還是小堆，怎么利用堆來給數(shù)組排序。

要進行升序就需要建大堆，如果建的是小堆，那么堆頂也就是首元素就是最小的元素，并不需要動，那么來處理第二個元素就注意到它并不一定是第二小的元素，只能從第二個元素開始重新建一個小堆，那么每排一個元素都需要重新建一個小堆效率就會變得很低。

升序建大堆的話，第一個元素就是最大的元素，我們可以讓它與最后一個元素互換，然后把堆的元素個數(shù)減一(就是把最后一個元素當做是堆外)，最后把堆頂元素向下調(diào)整，反復(fù)操作直到堆的元素個數(shù)變?yōu)榱肆?。這樣一個數(shù)組就按升序排好了。

降序需要建小堆，原理和排升序相同這里就不在贅述。

代碼示例：

#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個數(shù)

用堆結(jié)構(gòu)的一個好處就在于，不需要排序就能高效的找出最小的前n個元素或最大的前n個元素，現(xiàn)在我們來利用堆來嘗試找出文件中最小的K個數(shù)，一個比較低效的一個方法就是把文件中涉及到的所以數(shù)據(jù)都取出來然后把它建成一個小堆，然后Pop出前k次，得到最小的k個數(shù)。但是如果這個數(shù)據(jù)非常的大呢，比如有上億個數(shù)據(jù)，那么就會消耗很大的內(nèi)存空間。

有一個很優(yōu)的方法就是只取出文件的前K個數(shù)建成一個大堆，也就是說這個堆只用儲K個元素，那么堆頂就是這個堆的最大元素，然后繼續(xù)遍歷文件每遍歷一個元素都與堆頂元素作比較，如果比堆頂元素小就更新一下堆頂元素(把小的那個變成堆頂元素)，然后進行向下調(diào)整，直到遍歷完整個文件，那么此時堆中的元素就是文件中最小的K個元素。此方法在時間復(fù)雜度上與上一方法差不多，但它大大的節(jié)省了空間。

代碼示例：

#include<stdio.h>
#include"Heap.h"
void CreateNDate()
{
	//造數(shù)據(jù)，寫入文件中
	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;
}

到此這篇關(guān)于C語言堆實現(xiàn)建堆算法和堆排序的文章就介紹到這了,更多相關(guān)C語言堆內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: