堆和堆排序

目录

  • 1.二叉树的顺序存储
  • 2.堆的性质
  • 3.堆的实现
    • 3.1 堆的插入(向上调整算法)
    • 3.2 堆向下调整算法
    • 3.3 堆的创建
    • 3.4 堆的删除
    • 3.5 全套代码
  • 4.堆排序
  • 5.Top-K问题

1.二叉树的顺序存储

顺序存储就是数组存储,一般使用数组只适合完全二叉树,因为不是完全二叉树会有空间上的浪费。在现实生活中,只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
在这里插入图片描述

2.堆的性质

小堆

堆是一棵完全二叉树
堆的父亲节点总是小于孩子节点
根节点最小

在这里插入图片描述

大堆

堆是一棵完全二叉树
堆的父亲节点总是大于孩子节点
根节点最大

在这里插入图片描述

3.堆的实现

3.1 堆的插入(向上调整算法)

方法:

1.先将元素插入到堆的末尾,即最后一个孩子处
2.插入后如果堆的性质遭到破坏,将新插入节点顺着双亲往上调整

时间复杂度:O(NlogN)

举例:先插入一个20到堆的末尾,再往上进行调整算法,直到满足堆
在这里插入图片描述

举例:先插入一个10到堆的末尾,再往上进行调整算法,直到满足堆
在这里插入图片描述
在这里插入图片描述

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;}}
}

3.2 堆向下调整算法

现在我们给出一个数组,逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

前提:左右子树必须是一个堆,才能调整
时间复杂度:O(N)

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

在这里插入图片描述
在这里插入图片描述

void AdjustDown(HPDataType* 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 = 2 * parent + 1;}elsebreak;}
}

3.3 堆的创建

下面我们给一个数组,这个数组逻辑上可以看成一棵完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。

根节点左右子树不是堆,我们怎么调整呢?

方法一:向下调整法
我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的数,就可以调整成堆
方法二:向上调整算法
我们把数组第一个元素看成是堆,然后利用循环构建堆

int a[]={ 4,2,8,1,5,6,9,7,2,7,9 };

向下调整算法
在这里插入图片描述

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(a, n, i);
}

向上调整算法
在这里插入图片描述

for (int i = 1; i < n; i++)
{Adjustup(a, i);
}

3.4 堆的删除

删除堆是删除堆顶的数据,将堆顶的数据跟最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。
在这里插入图片描述

3.5 全套代码

#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 HPInint(Heap* hph);//初始化
void HPDestroy(Heap* hph);//销毁
void HPPush(Heap* hph, HPDataType x);//插入
void HPPop(Heap* hph);//删除
HPDataType HPTop(Heap* hph);//取堆顶元素
bool HPEmpty(Heap* hph);//判空
int HeapSize(Heap* hp);//求个数void Adjustup(HPDataType* a, int child);//向上调整算法
void swap(HPDataType* p1, HPDataType* p2);//交换
void AdjustDown(HPDataType* a, int n, int parent);//向下调整算法#include "Heap.h"void HPInint(Heap* hph)
{assert(hph);hph->a = NULL;hph->capacity = hph->size = 0;
}void HPDestroy(Heap* hph)
{assert(hph);free(hph->a);hph->a = NULL;hph->capacity = hph->size = 0;
}void swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//时间复杂度:NlogN
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 AdjustDown(HPDataType* 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 = 2 * parent + 1;}elsebreak;}
}void HPPush(Heap* hph, HPDataType x)
{assert(hph);//扩容if (hph->capacity == hph->size){int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(hph->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}//扩容成功hph->a = tmp;hph->capacity = newcapacity;}hph->a[hph->size] = x;hph->size++;//向上调整Adjustup(hph->a, hph->size - 1);
}void HPPop(Heap* hph)
{assert(hph);assert(hph->size > 0);swap(&hph->a[0], &hph->a[hph->size - 1]);hph->size--;//向下调整AdjustDown(hph->a, hph->size, 0);
}HPDataType HPTop(Heap* hph)
{assert(hph);assert(hph->size > 0);return hph->a[0];
}
bool HPEmpty(Heap* hph)
{assert(hph);return hph->size == 0;
}int HeapSize(Heap* hph)
{assert(hph);return hph->size;
}

4.堆排序

堆排序是利用堆积树这种结构所设计的一种排序的算法,它是选择排序的一种。

排升序建大堆
排降序建小堆
时间复杂度:O(Nlog N)

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--;}
}

5.Top-K问题

求数据结合中前k个最大的元素或者最小的元素,一般情况下数据量都比较大。
eg:专业前10名,世界500强等
对于top-k问题,能想到最简单的问题就是排序,但是:如果数据量非常大,排序就不可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决

  • 用数据集合中前k个元素建堆
    • 前k个最大元素,建小堆
    • 前k个最小元素,建大堆
  • 用剩余的N-K个元素一次与堆顶元素相比较,不满足则替换堆顶元素
void PrintTopK(int* a, int n, int k)
{//升序,建大堆//降序,建小堆// 1. 建堆--用a中前k个元素建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则替换for (int i = k ; i < n; i++){if (a[i] > a[0]){a[0] = a[i];AdjustDown(a, k, 0);}}int end = k - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}//打印前k个最大的数for (int i = 0; i < 5; i++)printf("%d ", a[i]);
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

AI革命:生活无处不智能

AI革命&#xff1a;生活无处不智能 &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 博客首页 怒放吧德德 To记录领地 &#x1f31d;分享学习心得&#xff0…

回见,那果园

记不得何时开始骑行&#xff0c;何时开始爬山&#xff0c;何时偶遇洛师傅&#xff0c;何时进了那半山腰的果园。 似乎很远&#xff0c;又很近。 昨天打电话给果园的师傅&#xff0c;本意问问杏是否熟了&#xff0c;周末骑行过去、进山聊天顺道吃个新鲜。 洛师傅呵呵的笑…

电脑版网易云音乐听歌识曲

文章目录 流程 流程 电脑网易云音乐的搜索框旁边就是听歌识曲功能

NDIS小端口驱动开发(一)

在四种NDIS相关的驱动中&#xff0c;微型端口驱动(也经常翻译为为小端口驱动)位于驱动栈的底部&#xff0c;一般将它理解为NIC设备的驱动程序&#xff1a; 有几种类型的微型端口驱动程序类型&#xff1a; 无连接微型端口驱动程序用于控制无连接网络媒体 &#xff0c;如以太网的…

JMeter 常见易错问题

1、配置错误&#xff1a; 问题&#xff1a;线程组配置错误&#xff0c;例如设置了错误的线程数或循环次数。 解决方法&#xff1a;检查线程组的配置。确保线程数&#xff08;即并发用户数量&#xff09;设置正确&#xff0c;以及循环次数符合预期。如果要模拟不同类型的用户行…

arc-eager算法XJTU-NLP自然语言处理技术期末考知识点

arc-eager算法&#xff1a;以我/做了/一个/梦为例来描述arc-eager算法的四个操作&#xff1a;shift&#xff0c;left-arc&#xff0c;right-arc&#xff0c;reduce XJTU-NLP期末考点2024版 题型&#xff1a;5*6简答题4*15计算题 简答题考点&#xff1a; &#xff08;1&#…

【30天精通Prometheus:一站式监控实战指南】第8天:redis_exporter从入门到实战:安装、配置详解与生产环境搭建指南,超详细

亲爱的读者们&#x1f44b;   欢迎加入【30天精通Prometheus】专栏&#xff01;&#x1f4da; 在这里&#xff0c;我们将探索Prometheus的强大功能&#xff0c;并将其应用于实际监控中。这个专栏都将为你提供宝贵的实战经验。&#x1f680;   Prometheus是云原生和DevOps的…

1301-习题1-1高等数学

1. 求下列函数的自然定义域 自然定义域就是使函数有意义的定义域。 常见自然定义域&#xff1a; 开根号 x \sqrt x x ​&#xff1a; x ≥ 0 x \ge 0 x≥0自变量为分式的分母 1 x \frac{1}{x} x1​&#xff1a; x ≠ 0 x \ne 0 x0三角函数 tan ⁡ x cot ⁡ x \tan x \cot x …

生产物流智能优化系统

对生产调度、物流调度【车辆路径问题、配送中心拣选问题】智能优化算法研究形成系统性程序&#xff0c;逐步开发设计一个智能优化系统【包括&#xff1a;问题说明、实验界面、算法结构和算法程序应用说明】&#xff0c; 当前完成TSP和集送车辆路径的算法程序&#xff0c;程序效…

Pandas高效数据清洗与转换技巧指南【数据预处理】

三、数据处理 1.合并数据&#xff08;join、merge、concat函数&#xff0c;append函数&#xff09; Concat()函数使用 1.concat操作可以将两个pandas表在垂直方向上进行粘合或者堆叠。 join属性为outer&#xff0c;或默认时&#xff0c;返回列名并集&#xff0c;如&#xff…

【大数据】MapReduce JAVA API编程实践及适用场景介绍

目录 1.前言 2.mapreduce编程示例 3.MapReduce适用场景 1.前言 本文是作者大数据系列专栏的其中一篇&#xff0c;前文我们依次聊了大数据的概论、分布式文件系统、分布式数据库、以及计算引擎mapreduce核心概念以及工作原理。 书接上文&#xff0c;本文将会继续聊一下mapr…

K8S认证|CKA题库+答案| 17. 节点维护

17、节点维护 CKA v1.29.0模拟系统免费下载试用&#xff1a; 百度网盘&#xff1a;https://pan.baidu.com/s/1vVR_AK6MVK2Jrz0n0R2GoQ?pwdwbki 题目&#xff1a; 您必须在以下Cluster/Node上完成此考题&#xff1a; Cluster Ma…

无线领夹麦克风哪个品牌好?无线麦克风品牌排行榜前十名推荐

​在当今的数字化浪潮中&#xff0c;个人声音的传播和记录变得尤为重要。无论是会议中心、教室讲台还是户外探险&#xff0c;无线领夹麦克风以其卓越的便携性和连接稳定性&#xff0c;成为了人们沟通和表达的首选工具。面对市场上琳琅满目的无线麦克风选择&#xff0c;为了帮助…

Arduino下载与安装(Windows 10)

Arduino下载与安装(Windows 10) 官网 下载安装 打开官网&#xff0c;点击SOFTWARE&#xff0c;进入到软件下载界面&#xff0c;选择Windows 选择JUST DOWNLOAD 在弹出的界面中&#xff0c;填入电子邮件地址&#xff0c;勾选Privacy Policy&#xff0c;点击JUST DOWNLOAD即可 …

使用SDL_QT直接播放渲染YUV格式文件

0.前要 下载一个文件&#xff0c;名字为 400_300_25.mp4&#xff0c;我们用ffmplay.exe将其转化为yuv文件&#xff0c;具体操作如下&#xff1a; 进入cmd控制台&#xff0c;进入ffmplay.exe文件的目录下&#xff0c;输入ffmpeg -i 文件名.mp4 文件名.yuv 回车&#xff0c;会生…

Java进阶学习笔记15——接口概述

认识接口&#xff1a; Java提供了一个关键字Interface&#xff0c;用这个关键字我们可以定义一个特殊的结构&#xff1a;接口。 接口不能创建对象。 注意&#xff1a;接口不能创建对象&#xff0c;接口是用来被类实现&#xff08;implements&#xff09;的&#xff0c;实现接口…

kotlinx.coroutines.debug.AgentPremain

大家好 我是苏麟 . 项目引入AI大模型 debug 出现报错 设置 勾选

微调Llama3实现在线搜索引擎和RAG检索增强生成功能

视频中所出现的代码 Tavily SearchRAG 微调Llama3实现在线搜索引擎和RAG检索增强生成功能&#xff01;打造自己的perplexity和GPTs&#xff01;用PDF实现本地知识库_哔哩哔哩_bilibili 一.准备工作 1.安装环境 conda create --name unsloth_env python3.10 conda activate …

读书笔记-Java并发编程的艺术--持续更新中

文章目录 第1章 并发编程的挑战1.1 上下文切换1.1.1 多线程一定快吗1.1.2 如何减少上下文切换 1.2 死锁1.3 资源限制的挑战 第2章 Java并发机制的底层实现原理第3章 Java内存模型第4章 Java编发编程基础第5章 Java中的锁第6章 Java并发容器和框架第7章 Java中的13个原子操作类第…

不知道是该怎么引用多个函数片段?具体示例如代码

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…