堆排序(大根堆)
堆的定义如下,n个关键字序列[1...n]称为堆,当且仅当满足:
a(i)>=a(2i)且a(i)>=a(2i+1) 这个为大根堆
a(i)<=a(2i)且a(i)<=a(2i + 1) 这个为小根堆
通过建堆得到大根堆
大根堆 87,45,78,32,17,65,53,9 可以看成
87
45 78
32 17 65 53
9
也就相当于是完全二叉树






#include<stdio.h>
void headadjust(int a[], int k, int i);
void swap(int *i, int *j)//交换堆顶和堆底元素
{int temp = *i;*i = *j; *j = temp;
}
void buildmaxheap(int a[], int len)//建立大根堆
{int i = 0;for (i = len / 2; i > 0; i--)//从i=[n/2]~1,反复调整堆headadjust(a, i, len);
}
void headadjust(int a[], int k, int len)//调整堆
{int i = 0;a[0] = a[k];//相当与根节点的复制值for (i = k * 2; i <=len; i *= 2)//从i较大的子节点向下筛选{if (i < len && a[i] < a[i + 1])//左孩子跟右孩子的大小i++;if (a[0] >= a[i])//根结点的值大于左右孩子直接退出break;else{a[k] = a[i];//否则交换孩子与根节点的值k = i;}}a[k] = a[0];//被筛选的值放在最后位置
}
int main()//堆排序
{int i = 0;int a[] = {0,53,17,78,9,45,65,87,32};int sz = sizeof(a) / sizeof(a[0]);printf("原来的数组为\n");for (i = 1; i < sz; i++)printf("%d ", a[i]);buildmaxheap(a, sz-1);//初始建堆for (i = sz-1; i > 1; i--){swap(&a[i], &a[1]);//调用swap()函数交换堆顶和堆底元素,此时堆得性质被破坏headadjust(a, 1, i - 1);//把剩余的i-1个元素整理成堆}printf("\n排完序的数组为\n");for (i = 1; i < sz; i++)printf("%d ", a[i]);return 0;
}

相关文章:
堆排序(大根堆)
堆的定义如下,n个关键字序列[1...n]称为堆,当且仅当满足: a(i)>a(2i)且a(i)>a(2i1) 这个为大根堆 a(i)<a(2i)且a(i)<a(2i 1) 这个为小根堆 通过建堆得到大根堆 大根堆 87,45,78,32,17,65,53,9 可以看成 …...
Mybatis学习笔记3 在Web中应用Mybatis
Mybatis学习笔记2 增删改查及核心配置文件详解_biubiubiu0706的博客-CSDN博客 技术栈:HTMLServletMybatis 学习目标: 掌握mybatis在web应用中如何使用 Mybatis三大对对象的作用域和生命周期 关于Mybatis中三大对象的作用域和生命周期、 官网说明 ThreadLocal原理及使用 巩…...
软件测试之功能测试详解
一、功能测试概述 1)功能测试就是对产品的各功能进行验证,根据功能测试用例,逐项测试,检查产品是否达到用户要求的功能。 2)功能测试,根据产品特性、操作描述和用户方案,测试一个产品的特性和…...
javascript选取元素的范围,可以包含父级,也可以不包含父级
//函数可以选取元素的范围,对于要选取文本的非常方便,或选取特定的子节点 function getRange(element){//判断是否支持range范围选取var supdocument.implementation.hasFeature("Range","2.0");var also(typeof document.createRan…...
QGIS怎么修改源代码?持续更新...
修改配置文件保存位置 修改目的:放着和本地安装的其他QGIS共用一份配置文件 修改文件:core/qgsuserprofilemanager.cpp 修改位置:第37行 return basePath QDir::separator() "my_profiles";修改完毕后,再次生成一下…...
dev board sig技术文章:轻量系统适配ARM架构芯片平台
摘要:本文简单介绍OpenHarmony轻量系统移植,会分多篇 适合群体:想自己动手移植OpenHarmony轻量系统的朋友 开始尝试讲解一下系统的移植,主要是轻量系统,也可能会顺便讲下L1移植。 1.1移植类型 OpenHarmony轻量系统的…...
MyBatis之增删查改功能
文章目录 一、创建各种类二、MyBatis的各种功能 1、查询<select>2、增加<insert>3、修改<update>4、删除<delete>三、总结 前言 在MyBatis项目中编写代码实现对MySql数据库的增删查改 一、创建各种类 1、在Java包的mapper文件下创建一个接口 我创建…...
Leetcode算法入门与数组丨5. 数组二分查找
文章目录 1 二分查找算法2 二分查找细节3 二分查找两种思路3.1 直接法3.2 排除法 1 二分查找算法 二分查找算法是一种常用的查找算法,也被称为折半查找算法。它适用于有序数组的查找,并通过将待查找区间不断缩小一半的方式来快速定位目标值。 算法思想…...
拓扑关系如何管理?
在设备对接涂鸦的云端过程中,一部分设备由于自身资源或硬件配置,无法直接连接云端。而是需要通过网关进行中转,由网关代理实现和云端进行数据交互,间接实现设备接入云端。这样的设备也称为子设备。 要想实现网关代理子设备接入云…...
vue的由来、vue教程和M-V-VM架构思想、vue的使用、nodejs
vue vue的由来 vue教程和M-V-VM架构思想 vue的初步简单使用 nodejs vue的由来 # 1 HTML(5)、CSS(3)、JavaScript(ES5、ES6、ES11):编写一个个的页面 -> 给后端(PHP、Python、Go、Java) -> 后端嵌入模板语法 -> 后端渲染完数据 -> 返回数据给前端 ->…...
课程表 循环依赖 拓扑排序 go语言
学会拓扑排序题目的基本解法 res数组 记录上课顺序g 记录学了课程i 能解锁的课程jindeg 记录每个课程的入度q 记录入度为0的课程 for循环q去解放其他课程 本题来自力扣课程表 func findOrder(numCourses int, prerequisites [][]int) []int {res : []int{}//建一个二维数组记…...
【红包雨接口设计】
一、服务器地址 http://rb.atguigu.cn 二、公共请求头参数 参数名称类型是否必选描述tokenString是用户唯一标识 备注:为了方便我们今天演示,服务端接受所有token。 三、接口 1. 创建红包雨 请求方式:GET请求地址:/api/v1/se…...
SSL证书到期更换证书会影响排名吗?
在现代的数字化时代,网络安全和用户体验成为了网站运营商和开发者们需要高度关注的问题。SSL证书作为一种重要的安全协议,对网站的安全性和用户信任起着至关重要的作用。然而,随着SSL证书的有效期限届满,许多网站运营商面临着更换…...
前端常用库之-JavaScript工具库lodash
文章目录 前端常用库之-JavaScript工具库lodash一、什么是lodash二、安装三、lodash使用Lodash 的 pick() 函数介绍和使用react 实例demo:pick结合...展开运算符(spread operator) 前端常用库之-JavaScript工具库lodash 一、什么是lodash 官网: https:…...
Linux- execve()
execve() 是 Linux/UNIX 中的 exec 函数家族中的一个,它允许进程执行一个新的程序。具体地,execve() 替换当前进程的映像为新的程序映像。 函数原型如下: int execve(const char *pathname, char *const argv[], char *const envp[]);pathn…...
007 数据结构_堆——“C”
前言 本文将会向您介绍关于堆Heap的实现 具体步骤 tips:本文具体步骤的顺序并不是源代码的顺序 typedef int HPDataType; typedef struct Heap {HPDataType* _a;int _size;int _capacity; }Heap;初始化 void HeapCreate(Heap* hp, HPDataType* a, int n) {hp-&…...
zabbix的原理与安装
一、Zabbix介绍 1、zabbix 是什么? zabbix是一个开源的IT基础监控软件,能实时监控网络服务,服务器和网络设备的状态,如网络使用,CPU负载、磁盘空间等,主要是包括数据的收集、报警和通知的可视化界面zabbi…...
ReactNative中升级IOS 17版本Crash解决
ReactNative中升级IOS 17版本Crash解决 ReactNative中升级IOS 17版本Crash解决一、问题描述二、原因分析三、解决方案决策3.1 设置宽高为非零值3.2 使用新的UIGraphicsImageRenderer替换就版本的UIGraphicsBeginImageContext 四、可能使用到该API的三方库4.1 react-native-fast…...
MongoDB详解
一、MongoDB概述 MongoDB 是一个基于 分布式文件存储 的开源 NoSQL 数据库系统,由 C 编写的。MongoDB 提供了 面向文档 的存储方式,操作起来比较简单和容易,支持“无模式”的数据建模,可以存储比较复杂的数据类型,是一…...
【SpringCloud微服务全家桶学习笔记-服务注册zookeeper/consul】
SpringCloud微服务全家桶学习笔记 Eureka服务注册 gitee码云仓库 9.其他服务注册框架 (1)zookeeper安装与使用 zookeeper需安装在虚拟机上,建议使用CentOS,安装地址如下: zookeeper镜像源 选择第一个进入后下载ta…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
