【数据结构与算法】堆的实现(附源码)

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

堆的代码实现,数据结构与算法,java,算法,数据结构,堆,c语言 

目录

一.堆的概念及结构

二.接口实现

A.初始化  Heapinit   销毁 Heapdestroy

B.插入 Heappush 向上调整  AdjustUp

1.Heappush

2.AdjustUp

C.删除 Heappop  向下调整  AdjustDown

D.堆的判空  Heapempty  堆顶数据  Heaptop  堆的大小  Heapsize

三.源码

Heap.h

Heap.c

test.c


一.堆的概念及结构

1.概念

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

其实堆是一种二叉树,通常我们都是用数据表实现,也就是说堆的底层是数组,数组中的小标表示二叉树的节点,所以在实现堆之前,我们有必要了解完全二叉树中节点之间的关系

1.理解父节点 parent 和子节点 child;

2.了解父节点与子节点之间的关系:

   A.parent=(child-1)/2;

   B.左孩子child=2*parent+1;

   C.右孩子child=2*parent+2。

堆的代码实现,数据结构与算法,java,算法,数据结构,堆,c语言

二.接口实现

A.初始化  Heapinit   销毁 Heapdestroy

这里的初始化和销毁都很简单,相信这对学到堆的人并不是什么难事,和顺序表的操作是一样的,如果实在不理解的话,请看 ->  顺序表

B.插入 Heappush 向上调整  AdjustUp

1.Heappush

插入数据很简单,直接对数组赋值,然后 size 再加加就行了,但是在插入完数据后,我们得保证它是堆,所以这就需要用到向上调整这个函数。

2.AdjustUp

假设我们建的是大堆,我们将新插入的节点与它的父节点比较:

1.如果比它的父节点大,则与其交换,所以交换后的父节点就成为了子节点,再与其父节点比较,以此类推

2.如果child<=0 则结束循环

堆的代码实现,数据结构与算法,java,算法,数据结构,堆,c语言

void Swap(HPdatatype* p1, HPdatatype* p2)  //交换函数
{
	HPdatatype tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPdatatype* arr, int child)   //向上调整
{
	assert(arr);

	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void Heappush(Heap* php, HPdatatype x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPdatatype* tmp = (HPdatatype*)realloc(php->arr, 2 * sizeof(HPdatatype) * php->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		php->arr = tmp;
		php->capacity *= 2;
	}

	php->arr[php->size] = x;
	php->size++;

	AdjustUp(php->arr, php->size - 1);  //注意这里要传size-1,因为size表示的是下一个位置
}

C.删除 Heappop  向下调整  AdjustDown

1.删除的话,我们是要删除堆顶的数据,因为删除堆尾的数据并没有什么实际意义,删除就是让size--,但是堆顶数据的下标是0,所以在删除前应先交换堆顶和堆尾的数据

2.删除完后,还要保持它还是个堆,不能把后面的顺序搞乱了,要想达到这个目的,就需要使用到向下调整这个函数;

3.假设是大堆,向下调整是父节点与其较大的子节点比较,如果较大的那个子节点大于父节点,则二者交换,然后较大的子节点成为了新的父节点,当子节点的下标大于或是等于节点总数,也就是size时,就结束循环。

堆的代码实现,数据结构与算法,java,算法,数据结构,堆,c语言

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

D.堆的判空  Heapempty  堆顶数据  Heaptop  堆的大小  Heapsize

这些接口的实现都非常简单,博主就不在这里讲述了,可以参考后面的源码。


三.源码

Heap.h

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

#define MAX_MIN <   //通过改变这里的符号,可以决定是建大堆还是小堆

typedef int HPdatatype;

typedef struct Heap
{
	HPdatatype* arr;
	int size;
	int capacity;
}Heap;

void Heapinit(Heap* php);

void Swap(HPdatatype* p1, HPdatatype* p2);

void AdjustUp(HPdatatype* arr, int child);  //向上调整

void Heappush(Heap* php, HPdatatype x);

void AdjustDown(HPdatatype* arr, int parent, int n);  //向下调整

void Heappop(Heap* php);

HPdatatype Heaptop(Heap* php);

int Heapsize(Heap* php);

bool Heapempty(Heap* php);

void Heapdestroy(Heap* php);

Heap.c

#include "Heap.h"


void Heapinit(Heap* php)
{
	assert(php);

	php->arr = (HPdatatype*)malloc(sizeof(HPdatatype) * 4);
	if (php->arr == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	php->size = 0;
	php->capacity = 4;
}

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

///С

void AdjustUp(HPdatatype* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (arr[child] MAX_MIN arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

void Heappush(Heap* php, HPdatatype x)
{
	assert(php);

	if (php->size == php->capacity)   //插入前,判断数组是否已满
	{
		HPdatatype* tmp = (HPdatatype*)realloc(php->arr, 2 * sizeof(HPdatatype) * php->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		php->arr = tmp;
		php->capacity *= 2;
	}

	php->arr[php->size] = x;
	php->size++;

	AdjustUp(php->arr, php->size - 1);  //这里要传size-1
}

void AdjustDown(HPdatatype* arr, int parent, int n)
{
	assert(arr);

	int child = 2 * parent + 1;

	while (child < n)
	{
        //判断较大(较小)的子节点
		if ((child + 1) < n && arr[child + 1] MAX_MIN arr[child])  
		{
			child++;
		}

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

void Heappop(Heap* php)
{
	assert(php);
	assert(php->size);
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;

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

HPdatatype Heaptop(Heap* php)
{
	assert(php);
	assert(php->size);   //为空时不能取数据

	return php->arr[0];
}

int Heapsize(Heap* php)
{
	assert(php);

	return php->size;
}

bool Heapempty(Heap* php)
{
	assert(php);

	return php->size == 0;  //size==0即为空
}

void Heapdestroy(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->size = 0;
	php->capacity = 0;
}

test.c

#include "Heap.h"


void testHeap()
{
	Heap hp;
	Heapinit(&hp);

	int i = 0, n = 10;
	int x = 0;
	while (n)
	{
		x = rand() % 100 + 1;

		Heappush(&hp, x);
		n--;
	}
	while (!Heapempty(&hp))
	{
		printf("%d  ", Heaptop(&hp));
		Heappop(&hp);
	}

	printf("\n");
	Heapdestroy(&hp);
}

int main()
{
	srand((unsigned int)time(NULL));
	testHeap();

	return 0;
}

🐲👻这循环队列的讲解就到这里了,若有错误或是建议欢迎小伙伴们指出。🐯🤖

🥰🤩希望小伙伴们可以多多支持博主哦。😍😃

😁😄谢谢你的阅读。😼😸

堆的代码实现,数据结构与算法,java,算法,数据结构,堆,c语言

 

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

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

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

相关文章

  • 【数据结构】堆:堆的构建,堆的向上调整算法,堆的向下调整算法、堆排序

    目录 一、堆的定义 1、堆的定义: 2、根节点与其左、右孩子间的联系   二、堆的创建 1、堆的向下调整算法  2、堆的向上调整算法  三、堆排序 1、堆的定义: 堆可以被看作是 一棵 完全二叉树 的 数组 对象 。即在 存储结构上是数组,在逻辑结构上是一棵完全二叉树 。在

    2024年01月22日
    浏览(43)
  • 数据结构:堆的实现

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

    2024年02月13日
    浏览(35)
  • 数据结构---堆的实现

    前言 一、什么是堆? 二、 堆的实现 1. 堆的结构  2. 接口实现 总结 堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。 现实中我们通常把 堆(一种二叉树) 使用 顺序结构的数组 来存储, 大根堆 :根节

    2024年02月02日
    浏览(39)
  • 数据结构之堆的结构与实现

    目录 一、堆的概念及结构 1.1堆的概念  1.2堆的性质 1.3堆的结构 二、堆的实现 2.1堆向下调整算法(父亲与孩子做比较)  2.2堆的向上调整算法(孩子与父亲做比较) 2.3堆的创建(向下建堆)  2.4向下建堆的时间复杂度 2.5堆的插入 2.6堆的删除 2.7堆的完整代码实现 三、堆的应

    2024年02月08日
    浏览(40)
  • 数据结构—小堆的实现

    前言:前面我们已经学习了二叉树,今天我们来学习堆,堆也是一个二叉树,堆有大堆有小堆,大堆父节点大于子节点,小堆父节点总小于子节点,我们在学习C语言的时候也有一个堆的概念,那个堆是操作系统中的堆,与我们今天所学的堆全然不同。我们就来实现下小堆。

    2024年02月05日
    浏览(34)
  • 数据结构:堆的实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 当一颗完全二叉树用顺序表来存储时,其被称为堆。 堆总是一棵完全二叉树 堆的某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值 其可以被用来解决top k 问题 或 堆排序 下面就是要实现的堆的功能 重点在

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

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

    2024年02月11日
    浏览(45)
  • 【数据结构之堆的实现】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续学习怎么实现基本的操作。所以先建议看完上篇知识点,才有助于消化知识和理解。 / 知识点汇总 / 概念 :堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看

    2024年01月19日
    浏览(43)
  • 【数据结构】堆的实现及应用

    简单不先于复杂,而是在复杂之后 。 1.1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系

    2024年02月21日
    浏览(48)
  • 【数据结构】结构实现:顺序存储模式实现堆的相关操作

    🚩 纸上得来终觉浅, 绝知此事要躬行。 🌟主页:June-Frost 🚀专栏:数据结构 🔥该文章着重讲解了使用顺序结构实现堆的插入和删除等操作。  二叉树的顺序存储是指将二叉树中的所有节点按照一定的顺序(一层一层)存储到一个数组中。  我们可以通过数组下标来表示

    2024年02月08日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包