当前位置: 首页 > article >正文

[数据结构]堆

堆,本质是一颗完全二叉树。属于非线性结构。

代码实现可参考树的代码。

函数介绍:

//此堆是小堆,大堆操作部分与小堆相反
void InitHeap(Heap* cat)
{
	assert(cat);
	cat->arr = NULL;
	cat->capacity = cat->size = 0;
}
void DestroyHeap(Heap* cat)
{
	assert(cat);
	if (cat->arr)
		free(cat->arr);
	cat->arr = NULL;
}
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
void AdjustUp(Type* arr, int child)//小堆
{
	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* cat, Type x)
{
	assert(cat);
	if (cat->capacity == cat->size)
	{
		int newcapacity = cat->capacity == 0 ? 4 : 2 * cat->capacity;
		Type* tmp = (Type*)realloc(cat->arr, newcapacity * sizeof(Type));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		cat->capacity = newcapacity;
		cat->arr = tmp;
	}
	cat->arr[cat->size++] = x;
	AdjutUp(cat->arr, cat->size);
}
void AdjustDown(Type* arr, int parent, int n)//小堆
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] > arr[child + 1])//找
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* cat)
{
	assert(cat);
	Swap(&cat->arr[0], &cat->arr[cat->size - 1]);
	--cat->size;
	AdjustDown(cat->arr, 0, cat->size - 1);
}
//判空
bool HeapEmpty(Heap* cat)
{
	assert(cat);
	return cat->size == 0;
}
//输出堆顶数据
Type HeapTop(Heap* cat)
{
	assert(cat);
	return cat->arr[0];
}
//打印堆可用三种遍历方式打印或者树的层序遍历,此处省略

头文件介绍:

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int Type;
typedef struct Heap {
	Type* arr;
	int capacity;
	int size;
}Heap;
void InitHeap(Heap* cat);
void DestroyHeap(Heap* cat);
void Swap(int* x, int* y);
void AdjustUp(Type* arr, int child);
void HeapPush(Heap* cat, Type x);
void AdjustDown(Type* arr, int parent, int n);
void HeapPop(Heap* cat);
bool HeapEmpty(Heap* cat);
Type HeapTop(Heap* cat);

谢谢观看!


http://www.kler.cn/a/371194.html

相关文章:

  • 智能文档处理平台:免费体验智能化医疗信息提取
  • 使用 Microsoft Clarity 记录分析用户行为
  • vue前端使用pdfjs与pdfdist-mergeofd 实现预览pdf并翻页,同时解决预览pdf显示模糊的问题
  • 微服务全链路监控中Trace和Span介绍
  • AI大模型与智算中心:构建未来智能社会的基石
  • Banana Pi BPI-R3路由器开发板运行 OrayOS物联网系统
  • 自然语言处理与文本分析及挖掘:原理、算法及应用场景介绍
  • HCIP-HarmonyOS Application Developer V1.0 笔记(一)
  • 初识WebGL
  • 使用 Microsoft Clarity 记录分析用户行为
  • Netty特点及相关面试题
  • 自动化部署-02-jenkins部署微服务
  • 抖音短剧小程序上线:短视频平台的全新娱乐体验
  • 力扣每日一题合集
  • 深入理解Redis的四种模式
  • 江协科技STM32学习- P24 DMA数据转运DMA+AD多通道
  • jupyter notebook 启动 Clusters 教程
  • .Net桌面程序开发框架汇总
  • 基于ResNet50模型的船型识别与分类系统研究
  • 智能工厂的设计软件 “word”篇、“power”篇和“task”篇
  • 【Linux】ClickHouse 部署
  • 计算机毕业设计Hadoop+大模型高考推荐系统 高考分数线预测 知识图谱 高考数据分析可视化 高考大数据 大数据毕业设计 Hadoop 深度学习
  • 石头剪刀布升级版[NOIP2014]
  • 聊一聊Elasticsearch的一些基本信息
  • 【数据结构 | PTA】与零交换
  • MATLAB基础应用精讲-【数模应用】PageRank(附R语言、MATLAB、Java和python代码实现)