当前位置: 首页 > 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;你可以返回一个更有意义…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

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…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用

阻止除自定义标签之外的所有标签 先输入一些标签测试&#xff0c;说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时&#xff08;如通过点击或键盘导航&…...