快捷導(dǎo)航

C語言實現(xiàn)堆的簡單操作的示例代碼

更新時間：2022年11月06日 14:35:54 作者：Fug_Lee

堆(heap)是計算機科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個可以被看做一棵樹的數(shù)組對象。本文介紹了C語言中堆的一些簡單操作，需要的可以參考一下

一、堆的概念

（1）定義

如果有一個關(guān)鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

（2）性質(zhì)

1.堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；

2.堆總是一棵完全二叉樹。

（3）小根堆示例圖

二、堆的實現(xiàn)

（1）堆的創(chuàng)建

例如：int a[ ] = {1,5,3,8,7,6};

a.初始化堆

b.交換3 和 6

c.交換5 和 8

d.交換1 和 8

調(diào)整1和8的位置，8的左子樹構(gòu)成的結(jié)構(gòu)被破壞，每一次調(diào)整元素的時候都有可能破壞其子堆的結(jié)構(gòu)。

（2）堆的插入

先將數(shù)字插入到數(shù)組的尾部，然后進行向上調(diào)整算法，直到滿足堆。

例如：在一個堆中插入80

（3）堆的刪除

刪除堆是刪除堆頂?shù)臄?shù)據(jù)，將堆頂?shù)臄?shù)據(jù)根最后一個數(shù)據(jù)一換，然后刪除數(shù)組最后一個數(shù)據(jù)，再進行向下調(diào)整算法。

三、堆的代碼實現(xiàn)

#include"common.h"
#define HeapDataType int
typedef struct Heap
{
	HeapDataType *base;
	int  capacity;
	int  size;
}Heap;
void HeapInit(Heap *php, int n);
void MinHeapInsert(Heap *php, HeapDataType x);
HeapDataType MinHeapRemove(Heap *php);
bool HeapEmpty(Heap *php);
void HeapPrint(Heap *php);
void HeapSort(Heap *php);
void AdjustUp(HeapDataType *base, int start);
void AdjustDown(HeapDataType *base, int start, int n);
void HeapInit(Heap *php, int n)
{
	assert(php != NULL);
	php->base = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
	assert(php->base != NULL);
	php->capacity = n;
	php->size = 0;
}
bool HeapEmpty(Heap *php)
{
	assert(php != NULL);
	return php->size == 0;
}
void MinHeapInsert(Heap *php, HeapDataType x)
{
	assert(php != NULL);
	if(php->size < php->capacity)
	{
		php->base[php->size] = x;
		AdjustUp(php->base, php->size);
		php->size++;
	}
}

HeapDataType MinHeapRemove(Heap *php)
{
	assert(php != NULL);
	assert(php->size > 0);
	int heaptop_val = php->base[0];
	php->size--;
	php->base[0] = php->base[php->size];
	AdjustDown(php->base, 0, php->size);
	return heaptop_val;
}

void HeapPrint(Heap *php)
{
	for(int i=0; i<php->size; ++i)
		printf("%d ", php->base[i]);
	printf("\n");
}

void AdjustUp(HeapDataType *base, int start)
{
	int j = start;
	int i = (j-1)/2;


	HeapDataType tmp = base[j];


	while(j > 0)
	{
		if(tmp < base[i])
		{
			base[j] = base[i]; 
			j = i;
			i = (j-1)/2;
		}
		else
			break;
	}
	base[j] = tmp;
}

void AdjustDown(HeapDataType *base, int start, int n)
{
	int i = start;
	int j = 2*i + 1;
	while(j < n)
	{
		if(j+1<n && base[j]>base[j+1]) 
			j++;
		if(base[i] > base[j])
		{
			Swap(&base[i], &base[j]);
			i = j;
			j = 2*i + 1;
		}
		else
			break;
	}
}
void HeapSort(Heap *php, int ar[], int n)
{
	for(int i=0; i<n; ++i)
		php->base[i] = ar[i];
	php->size = n;
	int curpos = n/2 - 1; 
	while(curpos >= 0)
	{
		AdjustDown(php->base, curpos, n);
		curpos--;
	}

	int end = n-1;
	while(end > 0)
	{
		Swap(&php->base[0], &php->base[end]);
		AdjustDown(php->base, 0, end);
		end--;
	}

	int k = php->size - 1;
	for(int i=0; i<n; ++i)
	{
		ar[i] = php->base[k--];
	}
}

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

您可能感興趣的文章: