堆排序算法及实现

1、堆排序定义

是一棵顺序存储完全二叉树

  • 其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆
  • 其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为根堆

举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:

  • Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
  • Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
大顶堆

 

堆特征:
  • 堆顶元素(完全二叉树的根)必为序列中n个元素的最小值或最大值
  • 堆中任何一个结点的非空左右子树都是一个堆
  • 根结点到任一个叶结点的每条路径上的结点值(关键字)都递减有序(或递增有序)

 堆排序需解决的2个问题

1、堆构建:如何由一个无序序列建成一个堆?

2、堆排序:如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆?

 2、堆构建

对待排序的记录,建成相应的完全二叉树从无序序列的第\left \lfloor n/2 \right \rfloor个元素(即此无序序列对应的完全二叉树的最后一个非终端结点)起,至第一个元素止,进行反复筛选。

3、堆排序 

定义:

将无序序列建成一个堆,得到关键字最小(或最大)的记录;

输出堆顶的最小(或最大)值后,使剩余的n-1个元素重又建成一个堆,则可得到n个元素的次小值;

重复执行,得到一个有序序列,这个过程叫堆排序。

排序过程:

1、输出堆顶元素之后,以堆中最后一个元素替代之;

2、然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换;重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选”。

 

4、算法实现 

#include <iostream>
#include <vector>

using namespace std;

//构建大顶堆
void HeapAdjust(vector<int> &list, int parent, int length){
	int temp = list[parent];					// temp保存当前父节点
	int child = 2 * parent + 1;					// 先获得左孩子

	while (child < length){
		// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
		if (child + 1 < length && list[child] < list[child + 1]){
			child++;
		}

		// 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
		if (temp >= list[child]){
			break;
		}

		// 把孩子结点的值赋给父结点
		list[parent] = list[child];

		// 选取孩子结点的左孩子结点,继续向下筛选
		parent = child;
		child = 2 * parent + 1;
	}
	list[parent] = temp;
}

//堆排序
vector<int> HeadSort(vector<int> list){
	int length = list.size();
	// 循环建立初始堆
	for (int i = length / 2 - 1; i >= 0; i--){
		HeapAdjust(list, i, length);
	}

	// 进行n-1次循环,完成排序
	for (int i = length - 1; i > 0; i--){
		// 最后一个元素和第一元素进行交换
		int temp = list[i];
		list[i] = list[0];
		list[0] = temp;

		// 筛选 R[0] 结点,得到i-1个结点的堆
		HeapAdjust(list, 0, i);
		cout << "第" << length - i << "趟排序:";
		for (int i = 0; i < list.size(); i++){
			cout << list[i] << " ";
		}
		cout << endl;
	}
	return list;
}

void main(){
	int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
	vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << "排序前:";
	for (int i = 0; i < test.size(); i++){
		cout << test[i] << " ";
	}
	cout << endl;
	vector<int> result;
	result = HeadSort(test);
	cout << "排序后:";
	for (int i = 0; i < result.size(); i++){
		cout << result[i] << " ";
	}
	cout << endl;
	system("pause");
}

 运行结果:

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

重温经典struts1之常用标签

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 前言 上一篇&#xff0c;我们学习了struts的基本概念&#xff0c;怎样搭建struts开发环境&#xff0c;从编写formbean&#xff0c;action到jsp页面&#xff0c;以及怎样将他…

用 Python 脚本实现电脑唤醒后自动拍照 截屏并发邮件通知

背景 背景是这样的, 我的家里台式机常年 休眠, 并配置了 Wake On Lan (WOL) 方便远程唤醒并使用。 但是我发现, 偶尔台式机会被其他情况唤醒, 这时候我并不知道, 结果白白运行了好几天, 浪费了很多电。 所以我的需求是这样的&#xff1a; &#x1f914; 电脑唤醒后(可能是开…

spider小案例~https://industry.cfi.cn/BCA0A4127A4128A4141.html

一、获取列表页信息 通过抓包发现列表页信息非正常返回&#xff0c;列表信息如下图&#xff1a; 通过观察发现列表页信息是通过unes函数进行处理的&#xff0c;我们接下来去看下该函数 该函数是对列表页的信息先全局替换"~"为"%u"&#xff0c;然后再通过…

人工智能(pytorch)搭建模型22-基于pytorch搭建SimpleBaseline(人体关键点检测)模型,并详细介绍该网络模型与代码实现

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能(pytorch)搭建模型22-基于pytorch搭建SimpleBaseline(人体关键点检测)模型&#xff0c;并详细介绍该网络模型与代码实现。本文将介绍关于SimpleBaseline模型的原理&#xff0c;以及利用pytorch框架搭建模型…

阿里面试:如何保证RocketMQ消息有序?如何解决RocketMQ消息积压?

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50)中&#xff0c;最近有小伙伴拿到了一线互联网企业如阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格&#xff0c;遇到很多很重要的面试题&#xff1a; 如何保证RocketMQ消息有序&#xff1f;如何解决RocketMQ消息…

Linux高级系统编程- 消息队列 与 内存共享

消息队列 消息队列是消息的链表&#xff0c;存放在内存中&#xff0c;由内核维护 特点&#xff1a; 1、消息队列中的消息是有类型的。 2、消息队列中的消息是有格式的。 3、消息队列可以实现消息的随机查询。消息不一定要以先进先出的次序读取&#xff0c;编程时 可以按消息的…

Python中的并发编程(3)线程池、锁

concurrent.futures 提供的线程池 concurrent.futures模块提供了线程池和进程池简化了多线程/进程操作。 线程池原理是用一个任务队列让多个线程从中获取任务执行&#xff0c;然后返回结果。 常见的用法是创建线程池&#xff0c;提交任务&#xff0c;等待完成并获取结果&…

Nginx正则表达式

目录 1.nginx常用的正则表达式 2.location location 大致可以分为三类 location 常用的匹配规则 location 优先级 location 示例说明 优先级总结 3.rewrite rewrite功能 rewrite跳转实现 rewrite执行顺序 语法格式 rewrite示例 实例1&#xff1a; 实例2&#xf…

2023年阿里云云栖大会-核心PPT资料下载

一、峰会简介 历经14届的云栖大会&#xff0c;是云计算产业的建设者、推动者、见证者。2023云栖大会以“科技、国际、年轻”为基调&#xff0c;以“计算&#xff0c;为了无法计算的价值”为主题&#xff0c;发挥科技平台汇聚作用&#xff0c;与云计算全产业链上下游的先锋代表…

网线市场现状与发展趋势预测

随着物联网、5G、云计算等技术的迅速发展&#xff0c;全球对于高速、稳定的网络需求急剧增长&#xff0c;这进一步推动了网线市场的发展。各种网络应用场景&#xff0c;从家庭到企业、数据中心到智能城市&#xff0c;都需要大量的高质量网线来支持数据传输和通信需求。本文将对…

LinuxBasicsForHackers笔记 -- 管理用户环境变量

查看和修改环境变量 env – 您可以通过从任何目录在终端中输入 env 来查看所有默认环境变量。环境变量的名称始终为大写&#xff0c;如 HOME、PATH、SHELL 等。 查看所有环境变量 set – 查看所有环境变量&#xff0c;包括 shell 变量、局部变量和 shell 函数&#xff08;例…

Axure的安装及基本功能介绍

目录 一. Axure概述 二. Axure安装 2.1 安装包下载 2.2 安装步骤 三. Axure功能介绍​ 3.1 工具栏介绍 3.1.1 复制&#xff0c;剪切及粘贴 3.1.2 选择模式和连接 3.1.3 插入形状 3.1.4 点&#xff08;编辑控点&#xff09; 3.1.5 置顶和置底 3.1.6 组合和取消组合 …

利用Rclone将阿里云对象存储迁移至雨云对象存储的教程,对象存储数据迁移教程

使用Rclone将阿里云对象存储(OSS)的文件全部迁移至雨云对象存储(ROS)的教程&#xff0c;其他的对象存储也可以参照本教程。 Rclone简介 Rclone 是一个用于和同步云平台同步文件和目录命令行工具。采用 Go 语言开发。 它允许在文件系统和云存储服务之间或在多个云存储服务之间…

RE2文本匹配调优实战

引言 在RE2文本匹配实战的最后&#xff0c;博主说过会结合词向量以及其他技巧来对效果进行调优&#xff0c;本篇文章对整个过程进行详细记录。其他文本匹配系列实战后续也会进行类似的调优&#xff0c;方法是一样的&#xff0c;不再赘述。 本文所用到的词向量可以在Gensim训练…

如何用CHAT写方案?

问CHAT&#xff1a;帮我写一份航空无动力乐园的可执行方案 CHAT回复&#xff1a; 方案一&#xff1a;概念及地点筛选 航空无动力乐园是指以航空运动为主题&#xff0c;利用自然地形与风力进行滑翔、跳伞等无动力航空运动的户外休闲娱乐乐园。鉴于此&#xff0c;首需要确定乐园…

Java入门项目--蚂蚁爱购

简介 这是一个靠谱的Java入门项目实战&#xff0c;名字叫蚂蚁爱购。 从零开发项目&#xff0c;视频加文档&#xff0c;十天就能学会开发JavaWeb项目&#xff0c;教程路线是&#xff1a;搭建环境> 安装软件> 创建项目> 添加依赖和配置> 通过表生成代码> 编写Ja…

力扣111. 二叉树的最小深度

给定一个二叉树&#xff0c;找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明&#xff1a;叶子节点是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;2 示例 2&#xff1a; 输入…

这样的Python自动化测试面试题,测开来了都不一定都会把!

十、接口自动化 10.1 接口自动化怎么测试 ( Python requestspytest 版本) 原来我们接口自动化是用 python request pytest 执行 接口自动化其实主要就是接口测试的基础上填加了断言&#xff0c;参数化&#xff0c;动态关联 做接口自动化之前&#xff0c;我们也会划分模块&#…

【数据结构】C语言实现堆(附完整运行代码)

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 一.了解项目功能 二.项目功能演示(以大堆为例) 三.逐步实现项目功能模块及其逻辑详解 1.实现堆程序主函数 2.创建堆结构 3.堆的初始化 4.数据元素入堆 5.数据元素…

Linux上编译和测试V8引擎源码

介绍 V8引擎是一款高性能的JavaScript引擎&#xff0c;广泛应用于Chrome浏览器和Node.js等项目中。在本篇博客中&#xff0c;我们将介绍如何在Linux系统上使用depot_tools工具编译和测试V8引擎源码。 步骤一&#xff1a;安装depot_tools depot_tools是一个用于Chromium开发…