C++实现小顶堆及堆排序完整代码

堆结构的定义与接口设计

为了实现一个动态大小的堆，我们需要封装一个结构体来管理底层的动态数组。本示例采用小顶堆的实现方式，即父节点的值总是小于或等于其子节点的值，这使得堆顶（数组第一个元素）始终是当前集合中的最小值。以下是 Heap.h 中定义的核心数据结构与函数原型：

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

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

//堆的向下调整算法
void AdjustDown(HPDataType* a, int n, int root);
//堆的向上调整算法
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);
//堆里的数据个数
int HeapSize(Heap* php);
//判断堆是否为空
int HeapEmpty(Heap* php);
//取堆顶数据
HPDataType HeapTop(Heap* php); 

堆操作接口的具体实现

堆的正确性依赖于两个核心调整算法：当新增元素时进行向上调整（AdjustUp），当移除或删除元素后进行向下调整（AdjustDown）。此外，初始化过程需要利用自底向上的向下调整算法来建立初始堆。

第1步：实现向下调整算法

目的：维持小顶堆性质，确保指定根节点的子树满足父子大小关系。入口为数组指针、节点总数和待调整的根节点索引。参数包括防止越界检查。完成状态为以该节点为根的子树恢复小顶堆形态。

#include "Heap.h"

//堆向下调整算法
//建小堆
void AdjustDown(HPDataType* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	//孩子超过数组下标结束
	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;
		}
	}
}

第2步：实现向上调整算法

目的：在新插入元素后，通过比较其与父节点的大小并交换位置，直到满足小顶堆条件。入口为新加入元素的索引。完成状态为该路径上的堆性质被修复。

//堆的向上调整算法
//建小堆
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;
		}
	}
}

第3步：实现初始化和销毁

目的：HeapInit负责分配内存并将原始数组拷贝至堆中，随后从最后一个非叶子节点开始执行向下调整以建立初始堆。HeapDestroy释放资源。注意在初始化完成后记录当前容量。

//堆的初始化
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;
}

第4步：实现插入与删除（堆排序关键）

目的：HeapPush在尾部添加元素并通过向上调整保持有序；HeapPop为实现堆排序的核心，它将堆顶（最小值）与末尾元素交换，缩小堆规模，再对新的堆顶进行向下调整。反复调用此方法即可得到从小到大的有序序列。

//堆的插入
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);
}
//堆里的数据个数
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}
//判断堆是否为空
//为空返回1，不为空返回0
int HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0 ? 1 : 0;
}
//取堆顶数据
HPDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

测试与堆排序结果

为了验证上述实现的正确性，我们构建一个测试函数 TestHeap。该函数初始化一组随机整数，建立小顶堆，然后循环取出堆顶元素并弹出。由于每次弹出的都是剩余元素中的最小值，最终输出的序列即为升序排列的数组。

#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++实现小顶堆及堆排序的详细代码实现与解析，更多关于C++数据结构与算法的资料请关注本站其它相关文章！