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

数据结构之二叉树——堆 详解(含代码实现)

1.堆

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

堆的性质:

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

创建堆

向上调整建堆

向下调整建堆

堆的插入

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆

向上调整算法

数组一个个循环插入时边插入边成堆,当插入新的元素时向上调整成新的堆

使用向上调整算法,每次孩子与父亲相比较,当孩子大于或小于父亲时进行交换,改变孩子的下标,再次进行判断然后交换,知道孩子的下标为0

堆的删除

向下调整算法

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

当已经成大堆或者小堆后想删元素,最好的办法是把堆的第一个元素与最后一个进行交换,当交换完成,堆中最大或最小的元素就到了最后一个结点,减小下标进行删除,此时堆顶的左右子树为大堆或者小堆,用向下调整算法,将父亲与孩子循环比较大小进行交换,形成新的堆,再次把堆顶元素与最后一个元素交换,使用向下调整成新的堆,反复进行即可删除堆

堆的排序   升序  降序

向上调整建堆,堆顶元素与最后一个元素交换,再次向上或向下调整,得到升序或降序

向上调整建堆

向下调整建堆

向上向下调整对比

向下调整时间复杂度分析

向上调整时间复杂度分析

总结

堆排序时间复杂度

堆的代码实现

//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
//初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
//向上调整
void Adjustup(HPDataType* a, int child);
//向下调整
void Adjustdown(HPDataType* a, int parent);
void swap(Heap* hp, int child, int parent);
//函数实现
#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
//初始化
void HeapInit(Heap* hp)
{assert(hp);hp->a = NULL;hp->size = hp->capacity = 0;
}
void swap( int *p1, int *p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
bool HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{free(hp->a);hp->a = NULL;free(hp);hp = NULL;
}
//向上调整
void Adjustup(HPDataType* a, int child)
{assert(a);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(Heap* hp, HPDataType x)
{assert(hp);if (hp->capacity == hp->size)//1未开劈空间 2.已满没有空间{int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;Heap* tmp = (Heap*)realloc(hp->a, sizeof(HPDataType)* newcapacity);if (tmp == NULL){perror("realloc fail");return NULL;}hp->a = tmp;hp->capacity = newcapacity;}//空间够  hp->a[hp->size] = x;hp->size++;//放进之后 向上调整形成新的堆Adjustup(hp->a, hp->size - 1);
}
//向xia调整
void Adjustdown(HPDataType* a,int n, int parent)
{assert(a);int child = parent * 2 + 1;while (child < n){     //右孩子小于huo大于左孩子if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[parent] > a[child]){swap(&a[child], &a[parent]);parent = child;child= parent * 2 + 1;}else {break;}}
}
// 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));//把第一个元素与最后一个交换,向下调整swap( &hp->a[0],&hp->a[hp->size-1]);hp->size--;Adjustdown(hp->a, hp->size, 0);}
//取堆顶数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp->size;
}
#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
void test()
{Heap hp;HeapInit(&hp);int a[] = { 60,50,6,8,14,7,3 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);}HeapDestroy(&hp);
}
void HeapSort(int* a, int n)
{// 升序 -- 建大堆// 降序 -- 建小堆Heap hp;HeapInit(&hp);//建堆--向上调整建堆/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*/// 建堆--向下调整建堆 --O(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;}
}
int main()
{test();return 0;
}

相关文章:

数据结构之二叉树——堆 详解(含代码实现)

1.堆 如果有一个关键码的集合 K { &#xff0c; &#xff0c; &#xff0c; … &#xff0c;}&#xff0c;把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中&#xff0c;则称为小堆( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆&#xff0c;根节点最小的…...

推荐一款面向增材制造的高效设计平台:nTopology

nTopology是一款面向增材制造的高效设计平台&#xff0c;平台预置了大量增材制造常用的设计工具包&#xff0c;工程师通过调用若干个预置工具包、或自主开发定制的工具包&#xff0c;建立一个工作流&#xff0c;实现复杂几何结构的参数化设计。nTopology集合了的强大几何建模和…...

SQL,力扣题目1767,寻找没有被执行的任务对【递归】

一、力扣链接 LeetCode_1767 二、题目描述 表&#xff1a;Tasks ------------------------- | Column Name | Type | ------------------------- | task_id | int | | subtasks_count | int | ------------------------- task_id 具有唯一值的列。 ta…...

JavaScript数据类型- Symbol 详解

文章目录 前言1.唯一性2. 描述3. 作为对象属性键4. 全局注册6. 不可变性7. 隐式转换 前言 Symbol是ES6新增内容&#xff0c;代表创建后独一无二且不可变的数据类型&#xff0c;它主要是为了解决可能出现的全局变量冲突的问题 在JavaScript发展的过程中&#xff0c;其中的ES6带…...

WordPress网站添加嵌入B站视频,自适应屏幕大小,取消自动播放

结合bv号 改成以下嵌入式代码&#xff08;自适应屏幕大小,取消自动播放&#xff09; <iframe style"width: 100%; aspect-ratio: 16/9;" src"//player.bilibili.com/player.html?isOutsidetrue&bvidBV13CSVYREpr&p1&autoplay0" scrolling…...

11.6 校内模拟赛总结

打的很顺的一场 复盘 7:40 开题&#xff0c;看到题目名很interesting T1 看起来很典&#xff0c;中位数显然考虑二分&#xff0c;然后就是最大子段和&#xff1b;T2 构造&#xff1f;一看数据范围这么小&#xff0c;感觉不是很难做&#xff1b;T3 神秘数据结构&#xff1b;T…...

Redis常用的五大数据类型(列表List,集合set)

简介 List 的特点&#xff1a;单键多值。底层实际是个双向链表&#xff0c;对两端的操作性能很高&#xff0c;通过索引下标的操作中间的节点性能会较差。 Redis 列表是简单的字符串列表&#xff0c;按照插入顺序排序。你可以添加一个元素到列表的头部&#xff08;左边&#xff…...

Ubuntu 20.04 部署向量数据库 Milvus + Attu

前言 最开始在自己的办公电脑&#xff08;无显卡的 windows 10 系统&#xff09; 上使用 Docker Desktop 部署了 Milvus 容器&#xff0c;方便的很&#xff0c; 下载 Attu 也很方便&#xff0c;直接就把这个向量数据库通过 Attu 这个图形化界面跑了起来&#xff0c;使用起来感…...

实现数传数据转网口(以太网)和遥控器SBUS信号转串口的功能

为了帮助你实现数传数据转网口&#xff08;以太网&#xff09;和SBUS信号转串口的功能&#xff0c;这里提供一个基本的框架。我们将使用STM32微控制器来完成这些任务。假设你已经具备了STM32的基本开发经验&#xff0c;并且已经安装了相应的开发环境&#xff08;如STM32CubeIDE…...

APP 后台广告位配置的关键要素与策略

在当今数字化营销的浪潮中&#xff0c;APP 作为重要的信息传播渠道&#xff0c;其后台广告位的配置显得尤为关键。这不仅影响着广告的展示效果&#xff0c;还直接关系到用户体验和平台收益。 首先&#xff0c;了解目标受众是配置广告位的基础。通过对 APP 用户的行为数据进行分…...

分布式数据库概述

分布式数据库概述 分布式数据库是一种将数据分散存储在多个物理节点上的数据库系统,这些节点通过网络相互连接,形成一个逻辑上统一的数据库系统。它旨在提高数据的可用性、可靠性、性能和可扩展性,是现代大数据和云计算环境下不可或缺的重要技术。 一、分布式数据库的核心…...

用通义灵码帮助实现校验bpmn.js当前画布上只能有一个开始节点的功能

最终代码&#xff1a; const elementRegistry this.bpmnModeler.get(elementRegistry);// 获取所有元素const allElements elementRegistry.getAll();// 过滤出开始节点const startEvents allElements.filter(element > element.type bpmn:StartEvent);// 校验开始节点的…...

OKHTTP断点续传

OKHTTP断点续传 文章目录 OKHTTP断点续传HTTP断点续传知识点RangeContent RangeEtag&If-Range&#xff08;文件唯一标志&#xff09; OKHTTP断点下载OKHTTP 简单短断点下载代码示例 Android 断点续传一直是面试的高频问点&#xff0c;这里从HTTP断点续传知识和Android续传思…...

软件测试学习笔记丨Flask操作数据库-ORM

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/23426 什么是持久化 是把数据保存到可永久保存的存储设备中&#xff08;比如磁盘&#xff09;。持久化的主要应用是将内存中的数据存储在关系型数据库中&#xff0c;当然也可以存储在磁盘文件…...

ABAP 开发的那些小技巧

在对话框程序中的选择屏幕添加图标 要在选择屏幕中添加图标&#xff0c;其中包括参数&#xff1a; 在参数的选择文本中或选择选项(select-option)中写入 01 或选择选项&#xff1a; 您可以使用 01、02、03&#xff0c;依此类推&#xff0c;以获取不同的不同图标。 在运行时…...

电科金仓(人大金仓)更新授权文件(致命错误: XX000: License file expired.)

问题:电科金仓(人大金仓)数据库链接异常,重启失败,查看日志如下: 致命错误: XX000: License file expired. 位置: PostmasterMain, postmaster.c:725 解决方法: 一、下载授权文件 根据安装版本在官网下载授权文件(电科金仓-成为世界卓越的数据库产品与服务提供商)…...

玩转「HF/魔搭/魔乐」平台

模型下载 Hugging Face 下载到 GitHub CodeSpace CodeSpace创建环境&#xff1a; # 安装transformers pip install transformers4.38 pip install sentencepiece0.1.99 pip install einops0.8.0 pip install protobuf5.27.2 pip install accelerate0.33.0下载internlm2_5-7b…...

鸿蒙系统的优势 开发 环境搭建 开发小示例

HarmonyOS是面向多智能终端、全场景的分布式操作系统,为消费者提供跨终端的无缝体验.华为开发者联盟从HarmonyOS应用设计、开发、测试、推广变现等环节全方位助力开发者。 开发者可以通过以下步骤学习鸿蒙系统的开发&#xff1a; 基础理论学习&#xff1a; 了解鸿蒙系统概述&a…...

python批量合并excel文件

当工作中发现有多个excel表需要进行相同的操作或者需要汇总在一起&#xff0c;一个一个处理太费时间&#xff0c;以下的python代码能够帮你解决这个问题~ import pandas as pd import os# 设置Excel文件所在的文件夹路径和合并文件的输出路径 folder_path D:\\Desktop\\dat…...

AWS S3 JavaScript SDK(v3)常用操作

安装 aws s3 sdk npm install aws-sdk/client-s3配置 创建 ~/.aws/credentials 文件&#xff0c;添加以下配置项&#xff1a; [default] aws_access_key_id<...> aws_secret_access_key<...> region<...>S3 SDK常用桶操作 获取桶列表 import {S3Client,…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...