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

49、PHP 实现堆排序

题目: PHP 实现堆排序

描述:

  • 堆排序
  • 基本思想:
  • 堆排序(HeapSort)是一树形选择排序。
  • 在排序过程中,将R[l…n]看成是一棵完全二叉树的顺序存储结构,
  • 利用完全二叉树中双亲结点和孩子结点之间的内在关系,
  • 在当前无序区中选择关键字最大(或最小)的记录。
  • 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
  • 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。
function heapSort(array $list){$length = count($list);buildHeap($list, $length - 1);while(--$length){$temp = $list[0];$list[0] = $list[$length];$list[$length] = $temp;heapAdjust($list, 0, $length);}return $list;
}function buildHeap(array &$list, $num){for($i = floor(($num - 1) / 2); $i >= 0; $i--){heapAdjust($list, $i, $num + 1);}
}function heapAdjust(array &$list, $i, $num){if($i > $num / 2){return ;}$key = $i;$leftChild = $i * 2 + 1;$rightChild = $i * 2 + 2;if ($leftChild < $num && $list[$leftChild] > $list[$key]) {$key = $leftChild;}if ($rightChild < $num && $list[$rightChild] > $list[$key]) {$key = $rightChild;}if ($key != $i) {$val = $list[$i];$list[$i] = $list[$key];$list[$key] = $val;heapAdjust($list, $key, $num);// heapPrint($list);}
}// function heapPrint(array $list){
// 	echo '<br>';
// 	echo 'Memory Structure:';
// 	echo '[ ' . implode(', ', $list) . ' ]';
// 	echo '<br>';
// 	echo 'Heap:';
// 	echo '<br>';
// 	$nbsp = '&nbsp;';
// 	$length = count($list);
// 	$level = ceil(sqrt($length));
// 	//start index
// 	for($j = 0; $j < $level; $j++){
// 		$startIndex = pow(2, $j) - 1;
// 		$endIndex = pow(2, $j) + $startIndex;
// 		for($i = $startIndex; $i < $endIndex; $i++){
// 			if($i < $length){
// 				echo $nbsp;
// 				echo $list[$i];
// 				echo $nbsp;
// 			}
// 		}
// 		echo '<br>';
// 	}
// }$list = array(3, 6, 2, 4, 10, 1 ,9, 8, 5, 7);
// heapPrint($list);
$result = heapSort($list);
// heapPrint($result);
var_dump($result);/*** 分析:* Memory Structure:[ 3, 6, 2, 4, 10, 1, 9, 8, 5, 7 ]* Heap:* 3 * 6  2 * 4  10  1  9 * 8  5  7 * * Memory Structure:[ 3, 6, 2, 8, 10, 1, 9, 4, 5, 7 ]* Heap:* 3 * 6  2 * 8  10 1  9 * 4  5  7 * Memory Structure:[ 3, 6, 9, 8, 10, 1, 2, 4, 5, 7 ]* Heap:* 3 * 6  9 * 8  10 1  2 * 4  5  7 * Memory Structure:[ 3, 10, 9, 8, 7, 1, 2, 4, 5, 6 ]* Heap:*  3 *  10  9 *  8  7  1  2 *  4  5  6 * Memory Structure:[ 3, 10, 9, 8, 7, 1, 2, 4, 5, 6 ]* Heap:*  3 *  10  9 *  8  7  1  2 *  4  5  6 * Memory Structure:[ 10, 8, 9, 5, 7, 1, 2, 4, 3, 6 ]* Heap:*  10 *  8  9 *  5  7  1  2 *  4  3  6 * Memory Structure:[ 10, 8, 9, 5, 7, 1, 2, 4, 3, 6 ]* Heap:*  10 *  8  9 *  5  7  1  2 *  4  3  6 * Memory Structure:[ 10, 8, 9, 5, 7, 1, 2, 4, 3, 6 ]* Heap:*  10 *  8  9 *  5  7  1  2 *  4  3  6 * Memory Structure:[ 9, 8, 6, 5, 7, 1, 2, 4, 3, 10 ]* Heap:*  9 *  8  6 *  5  7  1  2 *  4  3  10 * Memory Structure:[ 8, 7, 6, 5, 3, 1, 2, 4, 9, 10 ]* Heap:*  8 *  7  6 *  5  3  1  2 *  4  9  10 * Memory Structure:[ 8, 7, 6, 5, 3, 1, 2, 4, 9, 10 ]* Heap:*  8 *  7  6 *  5  3  1  2 *  4  9  10 * Memory Structure:[ 7, 5, 6, 4, 3, 1, 2, 8, 9, 10 ]* Heap:*  7 *  5  6 *  4  3  1  2 *  8  9  10 * Memory Structure:[ 7, 5, 6, 4, 3, 1, 2, 8, 9, 10 ]* Heap:*  7 *  5  6 *  4  3  1  2 *  8  9  10 * Memory Structure:[ 6, 5, 2, 4, 3, 1, 7, 8, 9, 10 ]* Heap:*  6 *  5  2 *  4  3  1  7 *  8  9  10 * Memory Structure:[ 5, 4, 2, 1, 3, 6, 7, 8, 9, 10 ]* Heap:*  5 *  4  2 *  1  3  6  7 *  8  9  10 * Memory Structure:[ 5, 4, 2, 1, 3, 6, 7, 8, 9, 10 ]* Heap:*  5 *  4  2 *  1  3  6  7 *  8  9  10 * Memory Structure:[ 4, 3, 2, 1, 5, 6, 7, 8, 9, 10 ]* Heap:*  4 *  3  2 *  1  5  6  7 *  8  9  10 * Memory Structure:[ 3, 1, 2, 4, 5, 6, 7, 8, 9, 10 ]* Heap:*  3 *  1  2 *  4  5  6  7 *  8  9  10 * Memory Structure:[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]* Heap:*  1 *  2  3 *  4  5  6  7 *  8  9  10 */

相关文章:

49、PHP 实现堆排序

题目&#xff1a; PHP 实现堆排序 描述&#xff1a; 堆排序基本思想:堆排序(HeapSort)是一树形选择排序。在排序过程中&#xff0c;将R[l…n]看成是一棵完全二叉树的顺序存储结构&#xff0c;利用完全二叉树中双亲结点和孩子结点之间的内在关系&#xff0c;在当前无序区中选择…...

鸿蒙9+在TV端焦点封装控制

鸿蒙9 目前不支持鸿蒙系统电视&#xff0c;但是往后肯定是必须会支持的&#xff0c;所以直接学arkts就完事了&#xff0c;目前的api9对焦点控制还是不够直接简洁&#xff0c;估计还在完善中&#xff0c;但是可以通过自定义component来实现一下 首先踩坑&#xff1a; Row官方说…...

操作系统课程设计:(JAVA)进程管理系统(附源码zip,jdk11,IDEA Ultimate2024 )

一.题目要求描述 本设计的目的是加深对进程概念及进程管理各部分内容的理解&#xff1b;熟悉进程管理中主要数据结构的设计及进程调度算法、进程控制机构、同步机构及通讯机构的实施。要求设计一个允许n个进程并发运行的进程管理模拟系统。 该系统包括有简单的进程控制、同步与…...

机器学习 | 回归算法原理——随机梯度下降法

Hi&#xff0c;大家好&#xff0c;我是半亩花海。接着上次的多重回归继续更新《白话机器学习的数学》这本书的学习笔记&#xff0c;在此分享随机梯度下降法这一回归算法原理。本章的回归算法原理还是基于《基于广告费预测点击量》项目&#xff0c;欢迎大家交流学习&#xff01;…...

LeetCode 面试经典 150 题 | 位运算

目录 1 什么是位运算&#xff1f;2 67. 二进制求和3 136. 只出现一次的数字4 137. 只出现一次的数字 II5 201. 数字范围按位与 1 什么是位运算&#xff1f; ✒️ 源自&#xff1a;位运算 - 菜鸟教程 在现代计算机中&#xff0c;所有数据都以二进制形式存储&#xff0c;…...

postMessage 收到消息类型 “webpackWarnings“

场景描述&#xff1a; 当A系统中的parent页面使用iframe内嵌C系统的child页面&#xff0c;并且在parent页面中通过postMessageg给child页面发送消息时&#xff0c;如果C系统中使用了webpack,则webpack也会给child页面发送消息 &#xff0c;消息类型为webpackWarnings。那么如何…...

计算机基础(day1)

1.什么是内存泄漏&#xff1f;什么是内存溢出&#xff1f;二者有什么区别&#xff1f; 2.了解的操作系统有哪些&#xff1f; Windows&#xff0c;Unix&#xff0c;Linux&#xff0c;Mac 3. 什么是局域网&#xff0c;广域网&#xff1f; 4.10M 兆宽带是什么意思&#xff1f;理论…...

cesium添加流动线

1&#xff1a;新建Spriteline1MaterialProperty.js文件 import * as Cesium from cesium;export function Spriteline1MaterialProperty(duration, image) {this._definitionChanged new Cesium.Event();this.duration duration;this.image image;this._time performance.…...

使用java自带的队列进行存取数据ArrayBlockingQueue 多线程读取ExecutorService

场景&#xff1a; 防止接收数据时处理不过来导致阻塞&#xff0c;使用ArrayBlockingQueue队列存储数据后&#xff0c;以多线程的方式处理数据 保证系统性能。 package com.yl.demo.main4;import java.text.SimpleDateFormat; import java.util.Date; import java.util.concurr…...

【音视频之SDL2】Windows配置SDL2项目模板

文章目录 前言 SDL2 简介核心功能 Windows配置SDL2项目模板下载SDL2编译好的文件VS配置SDL2 测试代码效果展示 总结 前言 在开发跨平台的音视频应用程序时&#xff0c;SDL2&#xff08;Simple DirectMedia Layer 2&#xff09;是一个备受欢迎的选择。SDL2 是一个开源库&#x…...

JavaScript 里的深拷贝和浅拷贝

JavaScript 里的深拷贝和浅拷贝 JS中数据类型分为基本数据类型和引用数据类型。 基本类型值指的是那些保存在栈内存中的简单数据段。包含Number&#xff0c;String&#xff0c;Boolean&#xff0c;Null&#xff0c;Undefined &#xff0c;Symbol。 引用类型值指的是那些保存…...

Oracle基础-集合

集合&#xff1a;两个结果集的字段个数和字段类型必须相同&#xff0c;才能使用集合操作。 --UNION 并集 重复行会去重 (SELECT A,B FROM DUAL UNION SELECT C,D FROM DUAL) UNION (SELECT A,B FROM DUAL UNION SELECT E,F FROM DUAL ); --UNION ALL 全集 包含所有记录 不去重…...

《浅谈如何培养树立正确的人工智能伦理观念》

目录 摘要&#xff1a; 一、引言 二、《机械公敌》的情节与主题概述 三、人工智能伦理与法律问题分析 1.伦理挑战 2.法律问题 四、培养正确的人工智能伦理观念的重要性 五、培养正确的人工智能伦理观念的途径与方法 1.加强教育与宣传 2.制定明确的伦理准则和规范 3.…...

uniapp实现局域网(内网)中APP自动检测版本,弹窗提醒升级

uniapp实现局域网&#xff08;内网&#xff09;中APP自动检测版本&#xff0c;弹窗提醒升级 在开发MES系统的过程中&#xff0c;涉及到了平板端APP的开发&#xff0c;既然是移动端的应用&#xff0c;那么肯定需要APP版本的自动更新功能。 查阅相关资料后&#xff0c;在uniapp的…...

【Golang 面试 - 进阶题】每日 3 题(六)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/UWz06 &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 Golang 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏…...

Unity横板动作游戏 -项目准备

项目准备 这是一篇 Unity 2022 最新稳定版本的教程同步笔记&#xff0c;本文将会讲解一些开始学习必须的条件。 安装环境 首先是安装 UnityHub&#xff0c;然后在 UnityHub 中安装 Unity 的版本(2022)。 只需要安装 开发者工具 和文档即可&#xff0c;导出到其他平台的工具等…...

基于Gunicorn + Flask + Docker的高并发部署策略

标题&#xff1a;基于Gunicorn Flask Docker的高并发部署策略 引言 随着互联网用户数量的增长&#xff0c;网站和应用程序需要能够处理越来越多的并发请求。Gunicorn 是一个 Python WSGI HTTP 服务器&#xff0c;Flask 是一个轻量级的 Web 应用框架&#xff0c;Docker 是一…...

jdk版本管理利器-sdkman

1.什么是sdkman&#xff1f; sdkman是一个轻量级、支持多平台的开源开发工具管理器&#xff0c;可以通过它安装任意主流发行版本&#xff08;例如OpenJDK、Kona、GraalVM等等&#xff09;的任意版本的JDK。通过下面的命令可以轻易安装sdkman: 2.安装 curl -s "https://…...

Kafka知识总结(事务+数据存储+请求模型+常见场景)

文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 文章收录在网站&#xff1a;http://hardyfish.top/ 事务 事务Producer保证消息写入分区的原子性&#xff0c;即这批消…...

C#中重写tospring方法

在C#中&#xff0c;重写ToString方法允许你自定义对象的字符串表示形式。当你想要打印对象或者在调试时查看对象的状态时&#xff0c;重写ToString方法非常有用。 默认情况下&#xff0c;ToString方法返回对象的类型名称。通过重写这个方法&#xff0c;你可以返回一个更有意义…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...