【二叉树的顺序结构：堆 堆排序 TopK]

news/2024/5/19 14:37:59 标签: 算法, 数据结构, c语言, 堆

努力提升自己，永远比仰望别人更有意义

目录

 

1 二叉树的顺序结构

2 堆的概念及结构

3 堆的实现

3.1 堆向下调整算法

 3.2 堆向上调整算法

 3.3堆的插入

 3.4 堆的删除

3.5 堆的代码实现

4 堆的应用

4.1 堆排序

4.2 TOP-K问题

总结：

1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2 堆的概念及结构

如果有一个关键码的集合 K = { k0 ，k1 ，k2 ，k3 … ，} ，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <=K2i+1 且 Ki<=K2i+2 ( i = 0 ， 1 ， 2… )，则称为小堆 (反之则大堆 ) 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树

3 堆的实现

3.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提： 左右子树必须是一个堆，才能调整。
int array [] = { 27 , 15 , 19 , 18 , 28 , 34 , 65 , 49 , 25 , 37 };

 具体代码：

void AdjustDown(int* a, int parent, int sz)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < sz)
	{
		if (child + 1 < sz && a[child + 1] > a[child])//建立小堆 a[child + 1] < a[child]
			child++;

		if (a[child] > a[parent])//建立小堆 <
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}

}

这里建立的是大堆，建立小堆代码中我给了注释.

 3.2 堆向上调整算法

堆的向上调整算法往往与push相搭配，push完一个数据就将该数据向上调整，这样就能够保证堆的结构不会被破坏。

具体图例：

代码实现：

void AdjustUp(int* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)//用parent>=0也行，只是这样的话就不是正常结束的了
	{
		if (a[child] > a[parent])//建小堆 <
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

 我们不难发现一个数据向上调整或者向下调整的时间复杂度都为logN.

 3.3堆的插入

具体图例：

 代码实现：

void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->sz)
	{
		int newcapacity = php->a == NULL ? 4 : php->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->sz] = x;
	php->sz++;
	//向上调整算法，保证建立的是堆（这里以建小堆为例）
	AdjustUp(php->a, php->sz - 1);//第二个参数传的是push这个数据的下标
}

 3.4 堆的删除

假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。

代码实现：

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->sz > 0);
	//假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，
	//否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。

	Swap(&php->a[0], &php->a[php->sz - 1]);
	php->sz--;
	AdjustDown(php->a, 0, php->sz);
}

3.5 堆的代码实现 

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

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* a;
	int sz;
	int capacity;
}Heap;

void HeapInit(Heap* php);
void HeapPush(Heap* php, HeapDataType x);
void HeapPop(Heap* php);
HeapDataType HeapTop(Heap* php);
int HeapSize(Heap* php);
bool HeapEmpty(Heap* php);
void HeapDestroy(Heap* php);
void HeapPrint(Heap* php);
void AdjustDown(int* a, int parent, int sz);
void AdjustUp(int* a, int child);
void Swap(HeapDataType* p1, HeapDataType* p2);

void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->sz = 0;
}


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


void AdjustUp(int* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)//用parent>=0也行，只是这样的话就不是正常结束的了
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}


void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->sz)
	{
		int newcapacity = php->a == NULL ? 4 : php->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->sz] = x;
	php->sz++;
	//向上调整算法，保证建立的是堆（这里以建小堆为例）
	AdjustUp(php->a, php->sz - 1);//第二个参数传的是push这个数据的下标
}


void AdjustDown(int* a, int parent, int sz)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < sz)
	{
		if (child + 1 < sz && a[child + 1] > a[child])
			child++;

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}

}


void HeapPop(Heap* php)
{
	assert(php);
	assert(php->sz > 0);
	//假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，
	//否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。

	Swap(&php->a[0], &php->a[php->sz - 1]);
	php->sz--;
	AdjustDown(php->a, 0, php->sz);
}


HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->sz > 0);

	return php->a[0];
	
}


int HeapSize(Heap* php)
{
	assert(php);
	return php->sz;
}


bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->sz == 0;
}


void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->capacity = php->sz = 0;
}


void HeapPrint(Heap* php)
{
	assert(php);
	for (int i = 0; i < php->sz; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

4 堆的应用

4.1 堆排序

在这里我们思考一个问题：排序是向上建堆还是向下建堆？

口说无凭，这里我们可以通过准确的计算来算出他们各自的时间复杂度：

1 向上建堆：

这里我们都以满二叉树为例，时间复杂度算的只是一个大概值所以可以用满二叉树来代替完全二叉树。（假设数的高度为h)

第一层有2^0个结点，要向上调整0次；

第二层有2^1个结点，要向上调整1次；

第三层有2^2个结点，要向上调整2次；

…………………………

第h-1层有2^(h-2)个结点，要向上调整(h-2)次；

第h层有2^(h-1)个结点，要向上调整(h-1)次；

所以可得：

T(h)=2^1*1+2^2*2+……2^(h-2)*(h-2)+2^(h-1)*(h-1)

利用错位相减法很容易算出：

T(h)=2^h*(h-2)+2;

由于h=logN(大概值就行，不用太精确）

所以求得向上建堆的时间复杂度大概在：

T(N)=N*logN  这个数量级。

2 向下建堆：

这个计算我在讲堆排序的时候计算过，大家可以跳转到堆排那里：

八大排序之插入和选择排序

通过计算我们可以知道向下建堆的时间复杂度大概在：

T(N)=N  这个数量级。

所以我们选用向下建堆。

那么第二个问题来了：排升序是建大堆还是建小堆？

如果建小堆，最小数已经被选出来了，但是不能够pop掉最小数，否则堆结构将被破环，那么又要重新建堆，这样就没有了效率，所以我们要建大堆，将堆顶元素与最后一个元素交换再--数据个数，然后向下调整。

具体代码：

void HeapSort(HeapDataType* a, int sz)
{
	//从最后一个结点的父亲开始建堆
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, sz);
	}

	for (int i = sz-1; i>0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, 0, --sz);
	}
}

4.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。
对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前 K 个元素来建堆 ：
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素 ：
将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。

具体代码：

    //建立一个k个数的小堆，依次遍历数组，比堆顶元素大就替换，然后向下调整,最后堆中数据就是topk
	//时间复杂度为：N+N*logk  空间复杂度为O(k)
	int topk[5] = {0};
	int i;
	for (i = 0; i < 5; i++)
	{
		topk[i] = array[i];
	}
	//建小堆
	for (i = (5 - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(topk, i, 5);
	}
	//遍历替换
	for (i=5; i < sz; i++)
	{
		if (array[i] > topk[0])
		{
			topk[0] = array[i];
			AdjustDown(topk, 0, 5);
		}
	}

	for (i = 0; i < 5; i++)
		printf("%d ", topk[i]);
	//这种方法占据内存较小，比较优秀

总结：

文章中我们介绍了堆这种二叉树顺序结构，实现了堆并且将堆的两大比较重要的应用（堆排序和TopK问题）介绍了，这里面比较重要的就是向上/向下调整算法。后面链式二叉树以及相关OJ我们将放在下一篇文章来讲解，大佬们，我们下期再见！

 


http://www.niftyadmin.cn/n/10490.html

相关文章

C++模拟OpenGL库——图形学状态机接口封装（二）：基于状态机接口的画线画三角形

C++模拟OpenGL库——图形学状态机接口封装（二）：基于状态机接口的画线画三角形

目录 画线操作 画三角形操作 按区间取点来进行绘制 加入纹理 画线操作 上次我们定义了一系列状态机接口&#xff0c;并遗留了&#xff1a; void Canvas::gtDrawArray(DRAW_MODE _mode, int _first, int _count) 没有去实现&#xff0c;这次对他进行一个实现&#xff0c;…
阅读更多...
栈的实现.

栈的实现.

文章目录1.栈的概念及结构2.栈的实现&#xff08;数组实现&#xff09;2.1栈头文件2.2函数实现3.栈的习题3.1有效的括号3.1.1思路分析3.1.2代码实现1.栈的概念及结构 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删…
阅读更多...
今天给大家介绍一篇基基于SSM超市管理系统的设计与实现

今天给大家介绍一篇基基于SSM超市管理系统的设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…
阅读更多...
ts泛型,映射,条件类型和类型提取infer和一些常用工具库的说明

ts泛型,映射,条件类型和类型提取infer和一些常用工具库的说明

Typescript当中的T,K,V到底是个啥 有时候,我们看到下面的代码,当然,这里是简单例子来说 function identity <T> (value:T) : T {return value; }其实泛型就是使用字母来代替将要接收的类型,这里的"T"是代表类型的缩写,表示对将要接收类型的一个占位符,占位符…
阅读更多...
渗透测试CTF-图片隐写的详细教程2(干货)

渗透测试CTF-图片隐写的详细教程2(干货)

上篇文章我们介绍了这7个工具&#xff0c;这里简单的介绍一下。 Binwalk 用来检测图片中是否有隐藏的文件。 Foremost 将图片中的隐藏文件拆分出来。 010Editor ①修改图片的参数来查看隐藏信息。 ②查看压缩包是否是伪加密。 Stegsolve.jar 图片隐写查看神器。 OurSecret 1个图…
阅读更多...
Google Earth Engine（GEE）—— geetool中的Widgets小部件(geetools:widgets)

Google Earth Engine（GEE）—— geetool中的Widgets小部件(geetools:widgets)

widgets module Custom widgets for the ui 用户界面的自定义小部件 To use it: var widgets = require(users/fitoprincipe/geetools:widgets)ClosePanel(options) A Panel with an X button for "closing" it. To make it work you must add it to another Pane…
阅读更多...
美国访问学者申请|J1签证官方指定材料大全

美国访问学者申请|J1签证官方指定材料大全

美国访问学者申请需要哪些材料&#xff1f;下面就随知识人网老师一起来看一看J1签证官方指定材料大全。 一、 有效护照&#xff1a;如果您的护照将在距您预计抵美日期的六个月内过期、或已损坏、或护照上已无空白的签证签发页, 请在前来面谈之前先申请一本新护照。 二、DS-160…
阅读更多...
react-window构造的虚拟列表使用react-resizable动态调整宽度和使用react-drag-listview拖拽变换列位置的问题

react-window构造的虚拟列表使用react-resizable动态调整宽度和使用react-drag-listview拖拽变换列位置的问题

文章目录react-window构造的虚拟列表使用react-resizable动态调整宽度和使用react-drag-listview拖拽变换列位置的问题需求问题问题根源部分代码参考react-window构造的虚拟列表使用react-resizable动态调整宽度和使用react-drag-listview拖拽变换列位置的问题 需求 项目中使…
阅读更多...
最新文章

Copyright @ 2022~2023