【数据结构 —— 堆的实现（顺序表）】

数据结构 —— 堆的实现（顺序表）

  • 一.堆
    • 1.1堆的定义及结构
      • 1.1.1.堆的定义
      • 1.1.2.堆的性质
      • 1.1.3.堆的结构
  • 二.堆的实现
    • 2.1.头文件的实现 —— （Heap.h）
    • 2.2.源文件的实现 —— （Heap.c）
      • 2.2.1.小堆的源文件
      • 2.2.2.大堆的源文件
    • 2.3.源文件的实现 —— （test.c）
  • 三.实际数据测试展示
    • 3.1.插入数据
      • 3.1.1.小堆插入 ——（调试窗口展示）
      • 3.1.2.大堆插入 ——（调试窗口展示）
    • 3.2 打印前k个最值 ——（小型top-k问题）
      • 3.2.1.小堆打印前k个最小值 —— （运行展示）
      • 3.2.2.大堆打印前k个最大值 —— （运行展示）
    • 3.3简单类堆排序 ——（非真堆排序）
      • 3.3.1.类小堆排序 ——（运行展示）
      • 3.3.2.类大堆排序 ——（运行展示）

一.堆

1.1堆的定义及结构

1.1.1.堆的定义

堆就是以二叉树的顺序存储方式来存储元素，同时又要满足父亲结点存储数据都要大于儿子结点存储数据（也可以是父亲结点数据都要小于儿子结点数据）的一种数据结构。堆只有两种即大堆和小堆，大堆就是父亲结点数据大于儿子结点数据，小堆则反之。

1.1.2.堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

1.1.3.堆的结构

用图画展示就如下图所示：
(1).小堆展示
在这里插入图片描述
(2).大堆展示
在这里插入图片描述

二.堆的实现

2.1.头文件的实现 —— （Heap.h）

Heap.h

#pragma once


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


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

//创建/销毁
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);

2.2.源文件的实现 —— （Heap.c）

2.2.1.小堆的源文件

Heap.c

#include"Heap.h"


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

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

//向上调整函数
void AdJustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	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)//判断数组空间不够就扩容
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdJustUp(php->a, php->size - 1);

}
//向下调整函数
void AdJustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1 < size && 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(HP* php)
{
	assert(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(php->size > 0);
	return php->a[0];

}
//判空/统计堆内元素个数
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
int HeapSize(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->size;
}

2.2.2.大堆的源文件

Heap.h

#include"Heap.h"


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

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

//向上调整函数
void AdJustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	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)//判断数组空间不够就扩容
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdJustUp(php->a, php->size - 1);

}
//向下调整函数
void AdJustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1 < size && 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(HP* php)
{
	assert(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(php->size > 0);
	return php->a[0];

}
//判空/统计堆内元素个数
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
int HeapSize(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->size;
}

2.3.源文件的实现 —— （test.c）

test.c

#include"Heap.h"

//小堆
int main()
{
	HP ph;
	HeapInit(&ph);

	int a[] = { 4,6,2,1,5,8,2,9};
	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++)
	{
		HeapPush(&ph, a[i]);//插入
	}

	//获取前k个最小值
	/*int k = 3;
	while (k--)
	{
		printf("%d\n", HeapTop(&ph));
		HeapPop(&ph);
	}*/
	//小堆排序
	while (!HeapEmpty(&ph))
	{
		printf("%d ", HeapTop(&ph));
		HeapPop(&ph);
	}

	return 0;
}

//大堆
//int main()
//{
//	HP ph;
//	HeapInit(&ph);
//	int a[] = { 4,6,2,1,5,8,2,9 };
//	for (int i = 0; i < (sizeof(a) / sizeof(int)); i++)
//	{
//		HeapPush(&ph, a[i]);
//	}
//	//前k个最大值
//	/*int k = 3;
//	while (k--)
//	{
//		printf("%d\n", HeapTop(&ph));
//		HeapPop(&ph);
//	}*/
//	//大堆排序
//	while(!HeapEmpty(&ph))
//	{
//		printf("%d ", HeapTop(&ph));
//		HeapPop(&ph);
//	}
//	return 0;
//}

三.实际数据测试展示

3.1.插入数据

3.1.1.小堆插入 ——（调试窗口展示）

在这里插入图片描述

3.1.2.大堆插入 ——（调试窗口展示）

在这里插入图片描述

3.2 打印前k个最值 ——（小型top-k问题）

3.2.1.小堆打印前k个最小值 —— （运行展示）

在这里插入图片描述

3.2.2.大堆打印前k个最大值 —— （运行展示）

在这里插入图片描述

3.3简单类堆排序 ——（非真堆排序）

3.3.1.类小堆排序 ——（运行展示）

在这里插入图片描述

3.3.2.类大堆排序 ——（运行展示）

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/186516.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Alibaba Cloud Linux 3安装Docker

Alibaba Cloud Linux 3安装Docker

进行docker安装&#xff08;以社区版为例&#xff09; 添加docker-ce的dnf源 dnf config-manager --add-repohttps://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo2.安装Alibaba Cloud Linux 3专用的dnf源兼容插件 dnf -y install dnf-plugin-releasever-adap…
阅读更多...
Ubuntu中安装搜狗输入法教程（详细图文教程）

Ubuntu中安装搜狗输入法教程（详细图文教程）

习惯了使用搜狗输入法&#xff0c;这里总结了Ubuntu系统下安装搜狗输入法的详细教程&#xff0c;每个步骤都很详细&#xff0c;耐心安装。 搜狗输入法是一款功能强大、使用方便的输入法&#xff0c;能够有效提升用户在Ubuntu系统中的输入体验。 目录 一、下载搜狗安装包1.1 搜…
阅读更多...
Python可迭代对象排序：深入排序算法与定制排序

Python可迭代对象排序：深入排序算法与定制排序

更多Python学习内容&#xff1a;ipengtao.com 排序在计算机科学中是一项基础而关键的操作&#xff0c;而Python提供了强大的排序工具来满足不同场景下的排序需求。本文将深入探讨Python中对可迭代对象进行排序的方法&#xff0c;涵盖基础排序算法、sorted函数的应用、以及定制排…
阅读更多...
算法-中等-链表-两数相加

算法-中等-链表-两数相加

记录一下算法题的学习11 两数相加 题目&#xff1a;给你两个非空的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照逆序的方式存储的&#xff0c;并且每个节点只能存储一位数字。请你将两个数相加&#xff0c;并以相同形式返回一个表示和的链表。你可以假设除了数字…
阅读更多...
物流实时数仓：数仓搭建（ODS）

物流实时数仓：数仓搭建（ODS）

系列文章目录 物流实时数仓&#xff1a;采集通道搭建 物流实时数仓&#xff1a;数仓搭建 文章目录 系列文章目录前言一、IDEA环境准备1.pom.xml2.目录创建 二、代码编写1.log4j.properties2.CreateEnvUtil.java3.KafkaUtil.java4.OdsApp.java 三、代码测试总结 前言 现在我们…
阅读更多...
Centos7 离线安装 CDH7.1.7

Centos7 离线安装 CDH7.1.7

1. 安装CDH的准备工作&#xff08;所有节点都要执行&#xff09; 1.1 准备环境 角色 IP k8s-master 192.168.181.129 k8s-node1 192.168.181.130 k8s-node2 192.168.181.131 1.2 安装JDK # https://www.oracle.com/java/technologies/downloads/#java11 wget rpm -ivh…
阅读更多...
C#，数值计算——插值和外推，Powvargram的计算方法与源程序

C#，数值计算——插值和外推，Powvargram的计算方法与源程序

1 文本格式 using System; namespace Legalsoft.Truffer { /// <summary> /// Functor for variogram v(r)ar^b, /// where b is specified, a is fitted from the data. /// </summary> public class Powvargram { private do…
阅读更多...
技术分享 | 在 IDE 插件开发中接入 JCEF 框架

技术分享 | 在 IDE 插件开发中接入 JCEF 框架

项目背景 当前的开发环境存在多种不同语言的 IDE&#xff0c;如 JetBrains 全家桶、Eclipse、Android Studio 和 VS Code 等等。由于每个 IDE 各有其特定的语言和平台要求&#xff0c;因此开发 IDE 插件时&#xff0c;需要投入大量资源才能尽可能覆盖大部分工具。同时&#xf…
阅读更多...
【精选】框架初探篇之——MyBatis的CRUD及配置文件

【精选】框架初探篇之——MyBatis的CRUD及配置文件

MyBatis增删改查 MyBatis新增 新增用户 持久层接口添加方法 void add(User user);映射文件添加标签 <insert id"add" parameterType"com.mybatis.pojo.User">insert into user(username,sex,address) values(# {username},# {sex},# {address}) <…
阅读更多...
SOLIDWORKS 2024新功能之CAM篇

SOLIDWORKS 2024新功能之CAM篇

SOLIDWORKS 2024 新功能 CAM篇目录概述 • 附加探测周期参数 • 反转切割的固定循环螺纹加工 • 包含装配体的零件的正确进给/速度数据 • Heidenhain 探测类型 • 2.5 轴特征向导中岛屿的终止条件 • 链接轮廓铣削操作的切入引导和切出引导参数 • 螺纹铣削操作的最小孔…
阅读更多...
从0开始学习JavaScript--深入了解JavaScript框架

从0开始学习JavaScript--深入了解JavaScript框架

JavaScript框架在现代Web开发中扮演着关键角色&#xff0c;为开发者提供了丰富的工具和抽象层&#xff0c;使得构建复杂的、高性能的Web应用变得更加容易。本文将深入探讨JavaScript框架的核心概念、常见框架的特点以及它们在实际应用中的使用。 JavaScript框架的作用 JavaSc…
阅读更多...
NX二次开发UF_CSYS_edit_matrix_of_object 函数介绍

NX二次开发UF_CSYS_edit_matrix_of_object 函数介绍

文章作者&#xff1a;里海 来源网站&#xff1a;https://blog.csdn.net/WangPaiFeiXingYuan UF_CSYS_edit_matrix_of_object Defined in: uf_csys.h int UF_CSYS_edit_matrix_of_object(tag_t object_id, tag_t matrix_id ) overview 概述 Updates the specified coordinat…
阅读更多...
Matplotlib自定义坐标刻度_Python数据分析与可视化

Matplotlib自定义坐标刻度_Python数据分析与可视化

自定义坐标刻度 主次要刻度隐藏刻度与标签花哨的刻度格式格式生成器与定位器 虽然matplotlib默认的坐标轴定位器与格式生成器可以满足大部分需求&#xff0c;但是并非对每一幅图都合适。 主次要刻度 学习前最好有对matplotlib图形的对象层级较为了解&#xff0c;例如查看前面…
阅读更多...
leetcode刷题详解三

leetcode刷题详解三

2. 两数相加 思路&#xff1a;直接加&#xff0c;注意进位条件不要用if&#xff0c;核心代码在于sum l1->val l2->val carry; ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* dummy new ListNode();ListNode* dummy_head dummy;int carry 0;int …
阅读更多...
Ubuntu 22.04.3编译AOSP13刷机

Ubuntu 22.04.3编译AOSP13刷机

文章目录 设备信息下载AOSP并切换分支获取设备驱动编译系统编译遇到的问题Cannot allocate memoryUbuntu设置USB调试刷机参考链接 设备信息 手机&#xff1a;Pixel 4XL 下载AOSP并切换分支 在清华大学开源软件镜像站下载初始化包aosp-latest.tar。 解压缩&#xff0c;切换到…
阅读更多...
【汉诺塔 —— （经典分治递归）】

【汉诺塔 —— （经典分治递归）】

汉诺塔 —— &#xff08;经典分治递归&#xff09; 一.汉诺塔介绍二.分治算法解决汉诺塔问题三.汉诺塔问题的代码实现四.主函数测试展示 一.汉诺塔介绍 汉诺塔问题源自印度一个古老的传说&#xff0c;印度教的“创造之神”梵天创造世界时做了 3 根金刚石柱&#xff0c;其中的一…
阅读更多...
机器视觉尺寸测量仪 助力打造智能工厂！

机器视觉尺寸测量仪 助力打造智能工厂！

摘要&#xff1a;机器视觉系统基本的特点就是提高生产的灵活性和自动化程度&#xff0c;目前机器视觉技术在蓬勃发展中&#xff0c;机器视觉尺寸测量仪是基于机器视觉原理制造而成的在线几何尺寸精密仪器。本文系统介绍一下该类测量设备。 机器视觉是什么&#xff1f; 简单来讲…
阅读更多...
从0开始学习JavaScript--JavaScript数据类型与数据结构

从0开始学习JavaScript--JavaScript数据类型与数据结构

JavaScript作为一门动态、弱类型的脚本语言&#xff0c;拥有丰富的数据类型和数据结构&#xff0c;这些构建了语言的基础&#xff0c;为开发者提供了灵活性和表达力。本文将深入探讨JavaScript中的各种数据类型&#xff0c;包括基本数据类型和复杂数据类型&#xff0c;并介绍常…
阅读更多...
2023.11.24制作一个常用的登录注册模板（包含密码验证、输出格式验证、验证码等功能）

2023.11.24制作一个常用的登录注册模板（包含密码验证、输出格式验证、验证码等功能）

2023.11.24制作一个常用的登录注册模板&#xff08;包含密码验证、输出格式验证、验证码等功能&#xff09; 1. 简介2. 功能3. 页面效果3.1 登录页面3.2 忘记密码页3.3 注册页面 1. 简介 比较喜欢简洁风&#xff0c;只是用bootstrap进行简单装饰 制作一个模板&#xff0c;日常…
阅读更多...
Leetcode---372周赛

Leetcode---372周赛

题目列表 2937. 使三个字符串相等 2938. 区分黑球与白球 2939. 最大异或乘积 2940. 找到 Alice 和 Bob 可以相遇的建筑 一、使三个字符串相等 这题把题目意思读懂&#xff0c;正常模拟就行&#xff0c;简单来说就是看三个字符串的最长公共前缀有多长&#xff0c; 代码如下…
阅读更多...
最新文章

Copyright @ 2022~2023