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

堆排序(大根堆)

堆的定义如下,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;
}

相关文章:

堆排序(大根堆)

堆的定义如下&#xff0c;n个关键字序列[1...n]称为堆&#xff0c;当且仅当满足&#xff1a; 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&#xff09;功能测试就是对产品的各功能进行验证&#xff0c;根据功能测试用例&#xff0c;逐项测试&#xff0c;检查产品是否达到用户要求的功能。 2&#xff09;功能测试&#xff0c;根据产品特性、操作描述和用户方案&#xff0c;测试一个产品的特性和…...

javascript选取元素的范围,可以包含父级,也可以不包含父级

//函数可以选取元素的范围&#xff0c;对于要选取文本的非常方便&#xff0c;或选取特定的子节点 function getRange(element){//判断是否支持range范围选取var supdocument.implementation.hasFeature("Range","2.0");var also(typeof document.createRan…...

QGIS怎么修改源代码?持续更新...

修改配置文件保存位置 修改目的&#xff1a;放着和本地安装的其他QGIS共用一份配置文件 修改文件&#xff1a;core/qgsuserprofilemanager.cpp 修改位置&#xff1a;第37行 return basePath QDir::separator() "my_profiles";修改完毕后&#xff0c;再次生成一下…...

dev board sig技术文章:轻量系统适配ARM架构芯片平台

摘要&#xff1a;本文简单介绍OpenHarmony轻量系统移植&#xff0c;会分多篇 适合群体&#xff1a;想自己动手移植OpenHarmony轻量系统的朋友 开始尝试讲解一下系统的移植&#xff0c;主要是轻量系统&#xff0c;也可能会顺便讲下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 二分查找算法 二分查找算法是一种常用的查找算法&#xff0c;也被称为折半查找算法。它适用于有序数组的查找&#xff0c;并通过将待查找区间不断缩小一半的方式来快速定位目标值。 算法思想…...

拓扑关系如何管理?

在设备对接涂鸦的云端过程中&#xff0c;一部分设备由于自身资源或硬件配置&#xff0c;无法直接连接云端。而是需要通过网关进行中转&#xff0c;由网关代理实现和云端进行数据交互&#xff0c;间接实现设备接入云端。这样的设备也称为子设备。 要想实现网关代理子设备接入云…...

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)&#xff1a;编写一个个的页面 -> 给后端(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是用户唯一标识 备注&#xff1a;为了方便我们今天演示&#xff0c;服务端接受所有token。 三、接口 1. 创建红包雨 请求方式&#xff1a;GET请求地址&#xff1a;/api/v1/se…...

SSL证书到期更换证书会影响排名吗?

在现代的数字化时代&#xff0c;网络安全和用户体验成为了网站运营商和开发者们需要高度关注的问题。SSL证书作为一种重要的安全协议&#xff0c;对网站的安全性和用户信任起着至关重要的作用。然而&#xff0c;随着SSL证书的有效期限届满&#xff0c;许多网站运营商面临着更换…...

前端常用库之-JavaScript工具库lodash

文章目录 前端常用库之-JavaScript工具库lodash一、什么是lodash二、安装三、lodash使用Lodash 的 pick() 函数介绍和使用react 实例demo&#xff1a;pick结合...展开运算符(spread operator) 前端常用库之-JavaScript工具库lodash 一、什么是lodash 官网&#xff1a; https:…...

Linux- execve()

execve() 是 Linux/UNIX 中的 exec 函数家族中的一个&#xff0c;它允许进程执行一个新的程序。具体地&#xff0c;execve() 替换当前进程的映像为新的程序映像。 函数原型如下&#xff1a; int execve(const char *pathname, char *const argv[], char *const envp[]);pathn…...

007 数据结构_堆——“C”

前言 本文将会向您介绍关于堆Heap的实现 具体步骤 tips&#xff1a;本文具体步骤的顺序并不是源代码的顺序 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 是什么&#xff1f; zabbix是一个开源的IT基础监控软件&#xff0c;能实时监控网络服务&#xff0c;服务器和网络设备的状态&#xff0c;如网络使用&#xff0c;CPU负载、磁盘空间等&#xff0c;主要是包括数据的收集、报警和通知的可视化界面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 数据库系统&#xff0c;由 C 编写的。MongoDB 提供了 面向文档 的存储方式&#xff0c;操作起来比较简单和容易&#xff0c;支持“无模式”的数据建模&#xff0c;可以存储比较复杂的数据类型&#xff0c;是一…...

【SpringCloud微服务全家桶学习笔记-服务注册zookeeper/consul】

SpringCloud微服务全家桶学习笔记 Eureka服务注册 gitee码云仓库 9.其他服务注册框架 &#xff08;1&#xff09;zookeeper安装与使用 zookeeper需安装在虚拟机上&#xff0c;建议使用CentOS&#xff0c;安装地址如下&#xff1a; zookeeper镜像源 选择第一个进入后下载ta…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...

TJCTF 2025

还以为是天津的。这个比较容易&#xff0c;虽然绕了点弯&#xff0c;可还是把CP AK了&#xff0c;不过我会的别人也会&#xff0c;还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...