admin管理员组

文章数量:1794759

【数据结构】二叉树顺序存储结构堆的应用以及解决TOP

前言

前面我们学习了堆这个数据结构，这种数据结构是一种顺序结构存储的完全二叉树，现在我们来看一看堆的应用。

1. 堆的应用

1.1 堆排序

版本一：基于已有数组建堆、取堆顶元素完成排序版本

代码语言：javascript代码运行次数：0运行复制
// 1、需要堆的数据结构
// 2、空间复杂度 O(N)
void HeapSort(int* a, int n)
{
	HP hp;
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, a[i]);
	}
	int i = 0;
	while (!HPEmpty(&hp))
	{
		a[i++] = HPTop(&hp);
		HPPop(&hp);
	}
	HPDestroy(&hp);
}

该版本有⼀个前提，必须提供有现成的数据结构堆

版本二：数组建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据

代码语言：javascript代码运行次数：0运行复制
// 升序，建大堆
// 降序，建小堆
// O(N*logN)
void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}
// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

堆排序时间复杂度计算

分析：

第1层，

2^0

个结点，交换到根结点后，需要向下移动0层

第2层，

2^1

个结点，交换到根结点后，需要向下移动1层

第3层，

2^2

个结点，交换到根结点后，需要向下移动2层

第4层，

2^3

个结点，交换到根结点后，需要向下移动3层

…

第h层，

2^{h-1}

个结点，交换到根结点后，需要向下移动h-1层

通过分析发现，堆排序第二个循环中的向下调整与建堆中的向上调整算法时间复杂度计算一致，此处不再赘述。因此，堆排序的时间复杂度为

O(n+n∗logn)

，即

O(nlogn)

本文标签： 数据结构二叉树顺序存储结构堆的应用以及解决TOP

版权声明：本文标题：【数据结构】二叉树顺序存储结构堆的应用以及解决TOP 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754680685a1705119.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。