【数据结构】二叉树——堆如何实现

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树——堆如何实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、二叉树的顺序结构

二、堆的概念及结构

三、堆的实现

四、堆的应用

4.1 堆排序

4.1.1 建堆

4.1.2 利用堆删除思想来进行排序

4.2 TOP-K问题

很多时候,我们竞争对手是我们自己,而不是别人。


一、二叉树的顺序结构

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

二、堆的概念及结构

如果有一个关键码的集合K ={ k0,k1,k2……,k(n-1)}【0,1,2,……,n-1这些都是下标】,把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki<=k(2*i+1)且Ki<=k2*i+2【Ki>=k(2*i+1)且Ki>=k(2*i+2)】i=0,1,2…,则称为小堆【或大堆】。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:1)堆中某个节点的值总是不大于或不小于其父节点的值;2)堆总是一棵完全二叉树。

理解堆分为大堆和小堆;大堆/大根堆:树中父亲的数据都大于等于孩子;小堆/小根堆:树中父亲的数据都小于等于孩子

堆解决的问题:堆排序、TOP-K

三、堆的实现

heap.h

#pragma once

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

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;

void HeapInit(HP* php);
void HeapDestory(HP* php);
void HeapPrint(HP* php);
void Swap(HPDataType* pa, HPDataType* pb);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);

heap.c


#include "heap.h"

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//按数组打印
void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
//多少个数据
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	//这个比较取决于大小堆
	//小堆
	//最后一次比较,是parent是0,进行比较,当再次进行调整后。就不需要进行了,此时的child等于0,parent也是0[因为size_t是正整数】
	//-1/2还是等于0
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;//跳出循环
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	数据插入数组后
	//先判断是否有地方进行扩容
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : (2 * (php->capacity));
		//开辟空间,要有一个临时变量进行开辟,否则如果开辟失败,里面的数据就都找不到了
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("malloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	(php->size)++;//先插入,后size++,此时size这个下标的位置并没有值
	向上调整的算法,成为堆
	size_t child = (php->size) - 1;
	AdjustUp(php->a, child);
}

 堆的插入:先插入一个数字到数组的尾上【插入的这个数字后,可能不满足堆的概念】,再进行向上调整算法,直到满足堆

void AdjustDown(HPDataType* a, size_t root, size_t size)
{
	//找出小的
	//注意:可能没有右孩子
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//避免越界
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//跳出循环
		}
	}
}

void HeapPop(HP* php)
{
	assert(php);
	//当删除数据的时候,要判断有没有值
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, 0, php->size);
}

堆的删除:删除堆是删除堆顶【最小或者最大的数据】的数据,将堆顶的数据最后一个数据换,然后删除数组最后一个数据,再进行向下调整算法。【先交,后删除,在进行向下调整算法】     

向下调整算法首先找出两个孩子节点中小(大)的那一个,然后去和父节点比较,进行交换,父节点的数据总是小于等于(大于等于)子节点,然后再从交换的孩子向下比较】

堆的插入、删除的时间复杂度为O(logN)  

四、堆的应用

4.1 堆排序

堆排序即利用 堆的思想来进行排序,总共分为两个步骤:
1. 建堆(在数组上建堆,那么堆排序的空间复杂度为O(1))
升序:建大堆
降序:建小堆
2. 利用堆删除思想来进行排序

4.1.1 建堆

 建堆有两种方法:(1)使用向上调整,插入数据的思想建堆。插入数据到新的数组,就是在不断插入的过程中向上调整实现排序 【代码1】(2)使用向下调整【从倒数第一个非叶子节点开始,即最后一个节点的父亲,即(size-1-1)/2】【找到这个父亲的节点,向下排序,然后这个父亲节点依次减一【就找到各个小堆】,依次向下排序,就成为了一个堆。】【代码2】

【建堆结束后,可以让数组成为一个堆】

代码1展示:

void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}


void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	//这个比较取决于大小堆
	//小堆
	//最后一次比较,是parent是0,进行比较,当再次进行调整后。就不需要进行了,此时的child等于0,parent也是0[因为size_t是正整数】
	//-1/2还是等于0
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;//跳出循环
		}
	}
}

void HeapSort(int* a, int n)
{
	//升序,建大堆,向上
	size_t i = 0;
	for (i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}
}

int main()
{
	int a[] = { 4, 3, 10 , 2, 5, 9 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

代码2展示:

void HeapSort(int* a, int n)
{
	//升序,建堆,向上
	/*int i = 0;
	for (i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}*/
    //向下
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, i, n);
	}
}

 建堆的时间复杂度:

向上建堆:首先每一层的节点数为2^(h-1);建堆是从第二层开始插入数据,第二层有2^(2-1)个节点,成为一个堆,向上调整的最坏次数为2^(2-1)*1;第三层有2^(3-1)个节点,成为一个堆,向上调整的次数为2^(3-1)*2;……;那么向上调整累积建堆次数为2^(2-1)*1+2^(3-1)*2+2^(4-1)*3+……+2^(h-1)*(h-1)。这是一个等差数列*等比数列。利用错位相减,可以算出次数为2^h*(h-2)+2; 最终时间复杂度为O(N*logN)

向下建堆:首先每一层的节点数为2^(h-1);建堆是从(从倒数第一个非叶子节点开始)【这个非叶子节点不一定是倒数第二层的最后一个,但是此时可以把堆看做满级二叉树【两者的时间复杂度,差别不大】,那么此时的非叶子节点就是倒数第二层的最后一个】倒数第二层开始向下调整,一直到第一层向下调整结束,每一层有2^(h-1)个节点,每一个节点和下面部分成为一个堆,每个节点向下调整的最坏次数为2^(h-1)*(h);那么向下调整累积建堆次数为2^0*(h-1)+2^1*(h-2)+2^2*(h-2)+……+2^(h-2)*1,这是一个等差数列*等比数列。利用错位相减,可以算出次数为2^h-1-h,因为2^h-1=N,; 最终时间复杂度为O(N).。

总结:建堆最好用向下建堆

建堆:升序建大堆,降序建小堆。【如果升序建小堆,最小的数已经在第一个位置了,再次选出次小的,需要不断建堆选数。那么总的时间复杂度为O(N^2),既然这样,还不如直接遍历选数,时间复杂度也是O(N^2)】【升序应该建大堆】

4.1.2 利用堆删除思想来进行排序

升序,大堆为例:建立大堆之后,最大值就在最前面,然后,最大值和最后一个值【下标为n-1】进行互换,然后不管n-1这个下标进行建堆,然后最大值再次与最后一个值进行【下标为n-2】进行互换。一直到下标为0的元素与下标为1的元素进行过交换,数组就完成了排序。【时间复杂度为:O(N*logN)】

void HeapSort(int* a, int n)
{
	//升序,建堆,向上
	/*int i = 0;
	for (i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}*/
    //向下
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; --i)
	{
		AdjustDown(a, i, n);
	}
    size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, 0, end);
		--end;
	}
}

4.2 TOP-K问题

 N个数找出最大/最小的前K个

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

时间复杂度为:O(K+logK*(N-K));空间复杂度为:O(K).文章来源地址https://www.toymoban.com/news/detail-548812.html

void PrintTopK(int* a, int n, int k)
{
	// 建堆--用a中前k个元素建堆
	int* kminHeap = (int*)malloc(sizeof(int) * k);
	if (kminHeap == NULL)
	{
		printf("malloc fail \n");
		exit(-1);
	}
	//前k个元素,放在数组里面
	for (int i = 0; i < k; ++i)
	{
		kminHeap[i] = a[i];
	}

	// 建小堆
	for (int j = (k - 2) / 2; j >= 0; --j)
	{
		AdjustDown(kminHeap, j, k);//k指的是下标,数组最后元素的下标,为了方便找到父节点
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
	for (int i = k; i < n; ++i)
	{
		if (a[i] > kminHeap[0])
		{
			kminHeap[0] = a[i];
			AdjustDown(kminHeap, 0, k);
		}
	}

	for (int j = 0; j < k; ++j)
	{
		printf("%d ", kminHeap[j]);
	}
	printf("\n");
	free(kminHeap);
}

void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2305] = 1000000 + 6;
	a[99] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[0] = 1000000 + 1000;
	PrintTopK(a, n, 10);
}

到了这里,关于【数据结构】二叉树——堆如何实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(40)
  • 【数据结构 —— 二叉树的链式结构实现】

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 1.有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 2.除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月05日
    浏览(54)
  • 数据结构-二叉树·堆(顺序结构的实现)

    🎉个人名片: 🐼作者简介:一名乐于分享在学习道路上收获的大二在校生 🐻‍❄个人主页🎉:GOTXX 🐼个人WeChat : ILXOXVJE 🐼本文由GOTXX原创,首发CSDN🎉🎉🎉 🕊系列专栏:零基础学习C语言----- 数据结构的学习之路 🐓每日一句:如果没有特别幸运,那就请特别努力!🎉

    2024年02月05日
    浏览(44)
  • 【数据结构—二叉树的链式结构实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、二叉树的存储结构 二、二叉树链式结构的实现 2.1手动构建一课树 2.2二叉树的遍历 三、二叉树链式结构的实现 3.1前序遍历(递归) 3.2中序遍历(递归) 3.3后序遍历(递归) 3.4层序遍历(非递

    2024年02月03日
    浏览(56)
  • 【数据结构】二叉树-堆(函数实现)

     🌈个人主页: 秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343 🔥 系列专栏: 《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482 ​​   目录 头文件 函数实现 初始化 销毁 插入 向上调整 交换两个元素 向下调整 删除(默认删堆顶元素) 找堆顶元素 堆的

    2024年01月22日
    浏览(40)
  • 数据结构——二叉树(堆的实现)

    目录   树概念及结构 树的相关概念 树的表示  二叉树的概念及结构   堆 堆的实现   结构体建立 初始化   添加元素  打印堆  删除堆首元素  返回首元素  判断是否为空 空间销毁  刷题找工作的好网站——牛客网 牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,

    2024年02月11日
    浏览(42)
  • 【数据结构】二叉树的实现

    一棵二叉树是结点的一个有限集合,该集合分为两点: 一是为空和二是由一个根节点加上两棵别称为左子树和右子树的二叉树组成从图上看出有2个性质: 二叉树不存在度大于2的结点 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树 对于任意的二叉树都是由以下

    2024年02月02日
    浏览(38)
  • 【数据结构】二叉树的链式结构及实现

    目录 1. 前置说明 2. 二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 3. 节点个数及高度等 4. 二叉树的创建和销毁 在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成

    2024年02月08日
    浏览(41)
  • 数据结构:二叉树的链式结构的实现

      目录  1.通过前序遍历构建二叉树 2. 二叉树的销毁  3.二叉树的遍历 4. 二叉树的节点个位和二叉树的叶子节点个位数 5. 二叉树的的k层节点数和查找值为x的节点 6. 判断二叉树是否为完全二叉树和求二叉树的高度h 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历

    2024年02月12日
    浏览(44)
  • 【数据结构】二叉树链式结构的实现(三)

    目录 一,二叉树的链式结构 二,二叉链的接口实现         1,二叉链的创建         2,接口函数         3,动态创立新结点         4,创建二叉树         5,前序遍历         6,中序遍历         7,后序遍历 三,结点个数以及高度等      

    2024年02月08日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包