完全二叉树——堆的概念及实现

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

前言

堆(heap):是堆内存的简称,堆是动态分配内存,内存大小不固定,也不会自动释放,堆——数据结构是一种无序的树状结构,同时它还满足key-value键值对的存储方式。

1. 堆的概念及结构

如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。
    完全二叉树——堆的概念及实现

2.堆的实现

2.1堆的向下调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

完全二叉树——堆的概念及实现

代码实现:

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
	int child = parent*2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}

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

	}
}

2.2堆的创建

下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。

int a[] = {1,5,3,8,7,6};

完全二叉树——堆的概念及实现
代码实现:

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

初始化:

//堆初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

2.3建堆时间复杂度

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):
完全二叉树——堆的概念及实现
因此,建堆的时间复杂度为:O(N).

2.4堆的插入

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
完全二叉树——堆的概念及实现

代码实现:

//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) >> 1;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) >> 1;
		}
		else
		{
			break;
		}
	}

}
//插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newCapacity = (php->capacity == 0) ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			return;
		}	
		php->a = tmp;
		php->capacity = newCapacity;
	}
	
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

完全二叉树——堆的概念及实现

2.5堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。
完全二叉树——堆的概念及实现
代码实现:

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
	int child = parent*2 + 1;
	while (child < n)
	{
		if (child + 1 < n && 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(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

3.堆的完整代码实现

Heap.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include <time.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(int* a, int n, int parent);

void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
// 
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

Heap.c

#include "Heap.h"

//交换两个元素
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) >> 1;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) >> 1;
		}
		else
		{
			break;
		}
	}

}


//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
	int child = parent*2 + 1;
	while (child < n)
	{
		if (child + 1 < n && 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 HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}


//销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php -> size = php->capacity = 0;
	free(php);
}

//插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newCapacity = (php->capacity == 0) ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			return;
		}	
		php->a = tmp;
		php->capacity = newCapacity;
	}
	
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}
// 删除堆顶数据
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}


//获取堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}

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

//获取堆的大小
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

Test.c文章来源地址https://www.toymoban.com/news/detail-469605.html

#include "Heap.h"

void Test()
{
	HP hp;
	HeapInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}

	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
	    printf("%d\n", top);
		HeapPop(&hp);
	}

}



void HeapSort(int* a, int n)
{
	//升序,建大堆
	//降序,建小堆
	//向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		//在调整,选出次小的数
		AdjustDown(a, end, 0);

		end--;
	}
}

void CreatData()
{
	//造数据
	int n = 1000;
	srand((unsigned int)time(NULL));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		printf("fopen fail");
		return;
	}

	for (size_t i = 0; i < n; i++)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
PrintTop(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		printf("fopen fail");
		return;
	}

	int* hipple = (int*)malloc(sizeof(int) * k);
	if (hipple == NULL)
	{
		printf("malloc fail");
		return;
	}

	for (size_t i = 0; i < k; i++)
	{
		fscanf(fout, "%d",&hipple[i]);
	}

	//建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(hipple, k, i);
	}

	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (hipple[0] < val)
		{
			hipple[0] = val;
			AdjustDown(hipple, k, 0);
		}

	}

	for (size_t i = 0; i < k; i++)
	{
		printf("%d ", hipple[i]);
	}
	printf("\n");
}

int main()
{
	//Test();
	/*int a[] = { 1,4,5,7,8,3,5,9,2 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}*/

	//CreatData();
	PrintTop(5);

	return 0;
}

总结

	通过本次堆的实现,加深了对堆这个结构的认识,同时了解了堆的实际应用——1.堆排序和2.TOP-K问题

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

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

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

相关文章

  • 【完全二叉树魔法:顺序结构实现堆的奇象】

    二叉树的顺序结构 堆的概念及结构 堆的实现 堆的调整算法 堆的创建 堆排序 TOP-K问题         普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储

    2024年02月07日
    浏览(38)
  • 【数据结构】树和二叉树的概念及结构

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

    2024年02月13日
    浏览(37)
  • 【数据结构】树和二叉树的概念及结构(一)

    目录 一,树的概念及结构         1,树的定义         2,树结点的分类及关系         3,树的表示 二,二叉树的概念及结构         1,二叉树的定义         2,特殊的二叉树         3,二叉树的性质         4,二叉树的存储结构 1,顺序存储

    2024年02月10日
    浏览(45)
  • 【数据结构】由完全二叉树引申出的堆的实现

    关于“堆”,百度百科上是这么说的: ——————————引自百度百科 由上面可知,我们可以将堆理解成一个数组,也可以理解成一个完全二叉树。 其实由于完全二叉树的特殊性,其本身就可以使用一个数组来存储。 在之前的二叉树的实现中,我们已经知道完全二叉树

    2024年02月08日
    浏览(43)
  • 数据结构 | 二叉树的概念及前中后序遍历

    下面内容来自百度百科 二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能

    2024年02月05日
    浏览(36)
  • 数据结构学习记录——什么是堆(优先队列、堆的概念、最大堆最小堆、优先队列的完全二叉树表示、堆的特性、堆的抽象数据类型描述)

    目录 优先队列 若采用数组或链表实现优先队列  数组 链表 有序数组 有序链表 总结 若采用二叉搜索树来实现优先队列 最大堆 堆的概念 优先队列的完全二叉树表示 堆的两个特性  结构性 有序性 【例】最大堆和最小堆 【例】不是堆 堆的抽象数据类型描述 优先队列 (Prio

    2024年02月02日
    浏览(49)
  • 树、二叉树概念(+堆的实现)

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 新的篇章的开始,是见证我的这一刻; 噢,这美好的一天; 是需要你来见证的! 我最亲爱的老铁们!!😊 要知道二叉树首先要知道 树 这 非线性 数据结构,它是由n(n≥0)个有

    2024年02月07日
    浏览(37)
  • 数据结构——二叉树(堆的实现)

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

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

     大佬们点点关注,点点赞?! 在上篇博客中我们已经介绍了树和二叉树的相关概念,相信大家都已经清楚了树和二叉树的基本思想,下面我们就来着重看看二叉树堆的实现。 在看堆的实现,我们先看看二叉树的顺序存储 二叉树的顺序存储就是以顺序表来实现的,也就是把

    2024年04月13日
    浏览(57)
  • 初识二叉树以及堆的简单实现

    目录 一:什么是树 【1】树的概念 【2】树的另外几个重要概念 【3】树的几种表示方法 二:什么是二叉树 【1】概念以及特点 【2】两种特殊的二叉树 【3】二叉树的性质 【4】二叉树的两种存储方式 三:堆的实现 我们前面所学的顺序表,链表都属于线性结构,而 树是一种非线性

    2023年04月09日
    浏览(21)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包