C语言实现堆的一些简单接口-创新互联

一.堆是什么？二.堆的简单接口如何实现？三.堆的意义？

//////

成都创新互联是一家集网站建设,景德镇企业网站建设,景德镇品牌网站建设,网站定制,景德镇网站建设报价,网络营销,网络优化,景德镇网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。1.堆是什么？

含义：堆实质上是用一维数组（比链表实现更优）存贮一种特殊的二叉树（完全二叉树）的一种顺序存贮方式；所以，堆总是一颗完全二叉树，而且堆还有大小堆之分；

大堆：根节点是堆中大的数，且每一个父节点总是大于等于自己的子节点；

小堆：根节点是堆中最小的数，且每一个父节点总是小于自己的子节点

如下图所示：（不一定是有序的数组，这只是方便举例）

/////

2.堆的简单接口实现

2.1 初始化堆：既然是用一维数组实现，根据之前对栈等线性表用数组实现的学习，我们应该知道此时需要用结构体来构建其结构，结构体中包含存贮完全二叉树中的节点信息的数组array，记录多少个节点的size，以及用来判断是否需要扩容的capacity;，具体代码如下所示：

//定义结构体，表示堆的信息：
typedef int typedata;
typedef struct HeapNode
{
	typedata* arr;
	int size;
	int capacity;
}HP;




//初始化堆
void HeapInit(HP* ps)//这里我没有先malloc空间，到后面插入的时候直接realloc就可以了；
{
	assert(ps);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

2.2 向堆中依次插入元素（向上调整法）：

//向堆中插入：
void swap(typedata* p1, typedata* p2)
{
	int temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}
void AdjustUP(typedata* ps, int child)
{
	int parent = (child - 1) / 2;//找到此时子节点的父节点，比较看是否需要向上调整；
	while (child >0)
	{
		if (ps[child] >ps[parent])//如果子节点的值大于父节点的值
		{
			swap(&ps[child], &ps[parent]);//交换函数：交换子节点与父节点的值；
			child = parent;//将父节点的数组下标给子节点，
			parent = (child - 1) / 2;//让子节点找到新的父节点，继续比较；
		}
		else
		{
			break;
		}
	}
}
void HeapPush(HP* ps, typedata x)
{
	assert(ps);

	//扩容:
	if (ps->size == ps->capacity)
	{
		ps->capacity = 0 ? 4 : ps->capacity * 2;
		typedata* ptr = realloc(ps->arr,sizeof(typedata) *(ps->capacity));
		if (ptr == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = ptr;
	}
	ps->arr[ps->size] = x;
	ps->size++;

	//向上调整建堆：
	AdjustUP(ps->arr, ps->size - 1);
}



//定义数组，调用插入接口依次插入：
int arr[10] = { 17,11,12,25,36,46,71,42,29,100 };
for (int i = 0; i< sizeof(arr) / sizeof(arr[0]); i++)
{
	//向堆中依次插入元素：
	HeapPush(&ps, arr[i]);
}

2.3 删除堆顶元素（向下调整法）：

void AdjustDown(typedata* ps, int n, int parent)
{
	assert(ps);
	int child = parent * 2 + 1;
	while (childps[parent])
		{
			swap(&ps[parent], &ps[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//删除堆顶元素接口：
void HeapPop(HP* ps)
{
	assert(!HeapEmpty(ps));
	swap(&ps->arr[0], &ps->arr[ps->size - 1]);//先将堆顶与堆底交换；
	ps->size--;//利用数组下标删除掉交换过来的堆顶；

	//向下调整建堆：
	AdjustDown(ps->arr, ps->size - 1, 0);

	
}

2.4 Topk问题（取堆中k个大或最小的元素）：

//Top(选取大或最小的元素)接口:
typedata HeapTop(HP* ps)//有返回值；
{
	assert(!HeapEmpty(ps));//调用判空接口对结构体判空
	return ps->arr[0];//返回堆顶元素；
}	


//Topk问题：取堆中大或最小的前K个元素：
int k = 5;
while(k--)
{
	printf("%d ", HeapTop(&ps));//调用Top接口，获取堆顶元素，并打印出来；
	HeapPop(&ps);//调用删除堆顶元素接口，删除掉打印过的堆顶，找堆中新的堆顶，实现多次寻找；
}

2.4 堆中元素个数，判空，打印以及销毁：

这几个接口比较简单，直接给出代码：

//判空：
bool HeapEmpty(HP* ps)
{
	assert(ps);
	return ps->size == 0;
}

//堆中元素个数：
size_t Heapsize(HP* ps)
{
	assert(!HeapEmpty(ps));
	return ps->size;
}

//打印堆：
void HeapPrint(HP* ps)
{
	assert(!HeapEmpty(ps));
	int i = 0;
	for (i = 0; i< ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//销毁堆：
void HeapDestroty(HP* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

/////

3，堆的意义？

意义：堆的意义在于存贮完全二叉树时同时可以通过堆排序（时间复杂度为O(n*log N)），快速的进行排序，此意义我将会在后面与其他几种排序中尽我大的能力去说明与理解；

/////

至此，这是我对堆的创建，堆的一些简单接口的实现的全部理解，如有不足之处，请各位大佬不吝赐教，谢谢！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：C语言实现堆的一些简单接口-创新互联
文章转载：http://scyanting.com/article/dchddc.html

C语言实现堆的一些简单接口-创新互联

其他资讯