快捷導航

C++實現(xiàn)堆排序示例

更新時間：2021年08月26日 16:43:45 作者：雙魚211

這篇文章主要介紹了C++實現(xiàn)堆排序示例，全文運用大量代碼完成堆排序，需要了解的朋友可以參考一下這篇文章

堆的實現(xiàn)

Heap.h 堆的管理及接口

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

//堆的向下調(diào)整算法
void AdjustDown(HPDataType* a, int n, int root);
//堆的向上調(diào)整算法
void AdjustUp(HPDataType* a, int child);
//堆的初始化
void HeapInit(Heap* php, HPDataType* a,int n);
//堆的銷毀
void HeapDestroy(Heap* php);
//堆的插入
void HeapPush(Heap* php, HPDataType x);
//堆的刪除
void HeapPop(Heap* php);
//堆里的數(shù)據(jù)個數(shù)
int HeapSize(Heap* php);
//判斷堆是否為空
int HeapEmpty(Heap* php);
//取堆頂數(shù)據(jù)
HPDataType HeapTop(Heap* php);

Heap.c 堆各個接口功能的實現(xiàn)

• 堆的插入：將x插入下標為size的位置，++size然后使用向上調(diào)整算法調(diào)整
• 堆的刪除(刪棧頂數(shù)據(jù))：將棧頂數(shù)據(jù)和下標為size-1位置的數(shù)據(jù)交換，然后–size,使用向下調(diào)整算法調(diào)整

#include "Heap.h"

//堆向下調(diào)整算法
//建小堆
void AdjustDown(HPDataType* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	//孩子超過數(shù)組下標結(jié)束
	while (child < n)
	{
		//child始終左右孩子中小的那個
		if (a[child + 1] < a[child] && child + 1 <n)//防止沒有右孩子
		{
			++child;
		}
		//小的往上浮，大的往下沉
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			parent = child;
			child = parent * 2 + 1;
		}
		//中途child>parent則已滿足小堆，直接break
		else
		{
			break;
		}
	}
}
//堆的向上調(diào)整算法
//建小堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			int tem = a[parent];
			a[parent] = a[child];
			a[child] = tem;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//堆的初始化
void HeapInit(Heap* php, HPDataType* a, int n)
{
	assert(php);
	assert(a);
	php->a = (HPDataType*)malloc(n * sizeof(HPDataType));
	if (php->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	for (int i = 0; i < n; i++)
	{
		php->a[i] = a[i];
	}
	//建堆
	for (int i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(php->a, n, i);
	}
	php->capacity = n;
	php->size = n;
}
//堆的銷毀
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
//堆的插入
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tem = (HPDataType*)realloc(php->a,php->capacity * 2 * sizeof(HPDataType));
		if (tem == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tem;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	++php->size;
	AdjustUp(php->a,php->size - 1);
}
//堆的刪除
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	HPDataType tem = php->a[php->size - 1];
	php->a[php->size - 1] = php->a[0];
	php->a[0] = tem;
	--php->size;
	AdjustDown(php->a, php->size, 0);
}
//堆里的數(shù)據(jù)個數(shù)
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}
//判斷堆是否為空
//為空返回1，不為空返回0
int HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0 ? 1 : 0;
}
//取堆頂數(shù)據(jù)
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

test.c測試

#include "Heap.h"

void TestHeap()
{
	int arr[] = { 27, 28, 65, 25, 15, 34, 19, 49, 18, 37 };
	Heap hp;
	HeapInit(&hp, arr, sizeof(arr)/sizeof(int));
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);

	}
	printf("\n");
	HeapDestroy(&hp);
}
int main()
{
	TestHeap();
	return 0;
}

以上就是C++實現(xiàn)堆排序示例的詳細內(nèi)容，更多關(guān)于C++實現(xiàn)堆排序的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: