当前位置: 首页 > 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…...

【滑动窗口】LCR 016. 无重复字符的最长子串

LCR 016. 无重复字符的最长子串 解题思路 窗口内的字符串就是不重复子串每次遇到新的字符 看看窗口内是否存在该字符 如果存在直接剔除 然后调整窗口左边界不存在 添加窗口内部 右边界 class Solution {public int lengthOfLongestSubstring(String s) {if(s.length() < …...

C++中将类成员函数作为变量传递给函数

假设类ClassName有一个成员函数 void ClassName::funcname(int);通过typedef定义一个类成员函数指针类型,参数和返回值类型都要与成员函数对应 typedef void (ClassName::*FuncPtr)(int); // 定义类成员函数指针获取到的参数就是 FuncPtr pf...

2024届数字IC设计秋招面经-鼎信

背景 985硕士&#xff0c;计算机科班&#xff0c;实验室做cpu设计和fpga算法加速&#xff0c;我做处理器安全方向&#xff0c;有项目。 投递 8.25 没有笔试&#xff0c;两轮面试&#xff0c;直接通知下周一面试&#xff0c;草草的准备了下。 一面 技术面 9.4 不到半小时 …...

【数据结构】二叉树的节点数,叶子数,第K层节点数,高度,查找x节点,判断是否为完全二叉树等方法

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

前馈神经网络(FFNN)和多层感知机(MLP)

多层感知器&#xff08;MLP, Multi-Layer Perceptron&#xff09;和前馈神经网络&#xff08;Feed-Forward Neural Network, FFNN&#xff09;是深度学习中两个经常被使用的术语&#xff0c;它们经常被互换使用。让我们详细地了解这两个术语&#xff1a; 多层感知器 (MLP): M…...

EasySwipeMenuLayout - 独立的侧滑删除

官网 GitHub - anzaizai/EasySwipeMenuLayout: A sliding menu library not just for recyclerview, but all views. 项目介绍 A sliding menu library not just for recyclerview, but all views. Recommended in conjunction with BaseRecyclerViewAdapterHelper Feature…...

优麒麟下载、安装、体验

下载 官网 优麒麟 点击增强版、或者基础版进行下载 虚拟机安装 选择镜像 修改名称和存储路径 设置为50G 下一步&#xff0c;点击完成 开启安装 设置语言 去掉下载更新选项 继续 点击restart now 输入密码 出现下图说明安装成功&#xff0c;可以畅快的使用了...

Appium混合页面点击方法tap的使用

原生应用开发&#xff0c;是在Android、IOS等移动平台上利用官方提供的开发语言、开发类库、开发工具进行App开发&#xff1b;HTML5&#xff08;h5&#xff09;应用开发&#xff0c;是利用Web技术进行的App开发。目前&#xff0c;市面上很多app都是原生和h5混合开发&#xff0c…...

求解灰度直方图,如何绘制灰度直方图(数字图像处理大题复习 P1)

文章目录 1. 画 X 轴2. 画直方图3. Complete 视频原链接 数字图像处理期末考试大题 B站链接 1. 画 X 轴 2. 画直方图 有几个 0 就在图上画多高&#xff0c;同理有几个 1 &#xff0c;X1 的地方就画多高 3. Complete 这里的情况比较平均&#xff0c;一般来说不会这么平均&a…...

8种结构型设计模式对比

一、适配器模式 简介 适配器模式是一种结构型设计模式&#xff0c;它用于将不兼容的接口转换为可兼容的接口。适配器模式允许两个不兼容的类能够协同工作&#xff0c;通过将一个类的接口转换为另一个类所期望的接口形式。这样就能够在不修改现有代码的情况下&#xff0c;使两…...

网站域名跟谁买/互联网广告营销是什么

这是一个缠绕了我差不多有大半年的噩梦,作为一个程序员,笔记本怎么可能不装linux系统,但是我的笔记本神舟系列,买回来屡次三番重装系统,废了很多功夫,网络连接那里一直就没有WiFi选项。 无奈之下,我一度把很多环境都迁移到windows里面去了,但是奈何ubuntu之心不死,总…...

织梦做的相亲网站/今日最新国内新闻重大事件

ntity Framework学习初级篇4--Entity SQL 时间:2010-02-05 博客园 ♂风车车.NetEntity SQl是ADO.NET实体框架提供的SQl类语言&#xff0c;用于支持实体数据模型(EDM)。Entity SQl可用于对象查询和使用EntityClient提供程序执行的查询。 l 关键字 Value关键字 ESQl提供了SELEC…...

wordpress停用谷歌字体/外贸建站与推广如何做

转自&#xff1a;https://cnodejs.org/topic/548e54d157fd3ae46b233502 Mongoose 是什么? 一般我们不直接用MongoDB的函数来操作MongoDB数据库 Mongose就是一套操作MongoDB数据库的接口. Schema 一种以文件形式存储的数据库模型骨架&#xff0c;无法直接通往数据库端&#xff…...

网站建设教程学校/凡科建站教程

使用exists函数和嵌套子查询&#xff0c;在大多数情况下使用exists函数而不是使用IN函数&#xff08;子结果很大用exists&#xff0c;很小用in&#xff09;。使用/*materialize*/with as 物化部分查询&#xff0c;避免展开产生误差执行计划。巧用分析函数&#xff0c;较少表的访…...

电商网站开发 数商云/快手seo

概述 有时候我们需要进行一些预处理和后处理&#xff0c;或者是拦截请求&#xff0c;在请求前后后做一些处理 使用Spring MVC框架&#xff0c;那么建议使用HandlerInterceptor&#xff0c;它可以类似于普通bean直接注册到Spring容器中被管理 HandlerInterceptor的三个抽象方法…...

什么样算网站需要备案/快排seo软件

最近在研究图像识别的时候遇到进制之间的转换&#xff0c;虽然之前也了解基二进制、八进制、十进制、十六进制之间转换的基本原理&#xff0c;但还没有在java里对其进行实现过。于是就对其进行了一翻研究&#xff0c;现将自己学习的总结与大家分享一下。 基本原理 二进制——…...