快捷導(dǎo)航

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)堆的基本操作實(shí)現(xiàn)

更新時(shí)間：2021年11月27日 17:20:58 作者：許同學(xué)。。

這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)堆的基本操作實(shí)現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

1.基本函數(shù)實(shí)現(xiàn)

a.代碼1(向下調(diào)整)

void AdjustDown(DateType*a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child<n)
	{
		if ((child+1) < n && a[child] > a[child + 1])
		{
			++child;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

注意:if里面的條件語(yǔ)句(child?+1)<n是防止越界的，因?yàn)椴荒鼙ＷC有右孩子。

b.代碼2(向上調(diào)整)

void AdjustUp(DateType*a , int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

注意:while里面的條件語(yǔ)句是不能夠?qū)懗?parent<0)，因?yàn)楫?dāng)child==0時(shí)，parent=(child - 1) / 2,parent==0,再次進(jìn)入循環(huán)不滿足a[child] < a[parent]，恰好跳出循環(huán)。如果寫成(a[child] <= a[parent])就死循環(huán)了

c.代碼3(交換）

void Swap(DateType*p1, DateType*p2)
{
	DateType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

2.建堆?

void CreatHeap(Heap*p,DateType*num,int n)
{
	assert(p);
	p->a = (DateType*)malloc(n * sizeof(DateType));
	if (p->a == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	memcpy(p->a, num, n * sizeof(DateType));
	p->size = n;
	p->capacity = n;
	//建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(p->a, p->size, i);
	}
}

3.插入數(shù)據(jù)

void HeapPush(Heap*p, DateType x)
{
	assert(p);
	if (p->size == p->capacity)
	{
		DateType*tmp = (DateType*)realloc(p->a, (p->capacity) * 2 * sizeof(DateType));
		if (tmp == NULL)
		{
			printf("realloc  failed\n ");
			exit(-1);
		}
	}
	(p->capacity) *= 2;
	p->a[p->size] = x;
	++(p->size);
	//向上調(diào)整
	AdjustUp(p->a, p->size-1);
}

4. 刪除數(shù)據(jù)

void HeapPop(Heap*p, DateType x)
{
	assert(p);
	Swap(&p->a[0], &p->a[p->size-1]);
	--(p->size);
	AdjustDown(p->a, p->size, 0);
	//左右子樹還是小堆，直接調(diào)整行了
}

把堆頂?shù)臄?shù)據(jù)與最后一個(gè)數(shù)據(jù)交換，再次調(diào)整size-1個(gè)數(shù)據(jù)。?

5.獲取堆頂?shù)臄?shù)據(jù)

DateType HeapTop(Heap*p)
{
	assert(p);
	return p->a[0];
}

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

int HeapSize(Heap*p)
{
	assert(p);
	return p->size;
}

7.判空

bool HeapIsEmpty(Heap*p)
{
	assert(p);
	return p->size == 0;
}

8.打印

void Print(Heap*p)
{
	assert(p);
	for (int i = 0; i < p->size; i++)
	{
		printf("%d ", (p->a)[i]);
	}
	printf("\n");
	int count = 0;//計(jì)數(shù)
	int levelsize = 1;
	for (int i = 0; i < p->size; i++)
	{
		printf("%d ", p->a[i]);
		++count;
		if (count == levelsize)
		{
			printf("\n");
			levelsize *= 2;
			count = 0;//重新計(jì)數(shù)
		}
	}
	printf("\n");
}

9.銷毀

void HeapDestory(Heap*p)
{
	assert(p);
	free(p->a);
	p->a = NULL;
	p->capacity = p->size = 0;
}

10.測(cè)試

int main()
{
	int num[] = { 12,15,17,23,10,25 };
	int n = sizeof(num) / sizeof(num[0]); 
	Heap a;
 	//創(chuàng)建小堆
	CreatHeap(&a,num, n);
	Print(&a);
	printf("\n"); 
	//插入數(shù)據(jù)
	HeapPush(&a, 1);
	Print(&a);
 	//刪除對(duì)頂?shù)臄?shù)據(jù)
	HeapPop(&a);
	Print(&a);
	printf("\n"); 
	//獲取堆頂數(shù)據(jù)
	int ret=HeapTop(&a);
	printf("The top date is %d\n",ret); 
	//堆的數(shù)據(jù)個(gè)數(shù)
	int number=HeapSize(&a);
	printf("The number of heap is %d\n", number); 
	//銷毀
	HeapDestory(&a); 
	return 0;
}

11.測(cè)試結(jié)果

12.用堆排序(降序)

a.代碼1

int main()
{
	DateType num[] = { 12,15,17,23,10,25 };
	int n = sizeof(num) / sizeof(num[0]);
	HeapSort(num, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", num[i]);
	}
	printf("\n\n");
	return 0;
}

void HeapSort(int*num, int n)
{
	//建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(num, n, i);
	}
	int end = n - 1;
	while (end>0)
	{
		Swap(&num[0], &num[end]);
		AdjustDown(num, end, 0);
		--end;
	}
}

運(yùn)行結(jié)果