二叉堆-堆排序

一 ：理解基础概念

1. 堆排序的基本概念

堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的排序算法。它的核心思想是通过构建一个最大堆或最小堆，利用堆的性质逐步将堆顶元素（最大值或最小值）取出，从而实现排序。

  • 二叉堆：

    • 二叉堆是一种完全二叉树（Complete Binary Tree），即除了最后一层，其他层都是满的，且最后一层的节点尽可能靠左排列。
    • 二叉堆分为两种：
      • 最大堆（Max Heap）：每个节点的值都大于或等于其子节点的值。堆顶元素是最大值。
      • 最小堆（Min Heap）：每个节点的值都小于或等于其子节点的值。堆顶元素是最小值。

  • 堆排序的核心思想：

    • 将待排序的数组构建成一个最大堆（或最小堆）。
    • 将堆顶元素（最大值或最小值）与堆的最后一个元素交换，然后将堆的大小减一。
    • 对剩余的堆进行调整，使其重新满足堆的性质。
    • 重复上述步骤，直到堆的大小为 1，排序完成。

2. 二叉堆的性质

二叉堆的性质是堆排序的基础，理解这些性质是掌握堆排序的关键。

最大堆的性质
  • 每个节点的值都大于或等于其子节点的值。
  • 堆顶元素是堆中的最大值。
  • 示例：
          10/  \7    8/ \  /5   6 3
    在这个最大堆中，每个父节点的值都大于其子节点的值。
最小堆的性质
  • 每个节点的值都小于或等于其子节点的值。
  • 堆顶元素是堆中的最小值。
  • 示例：
          1/  \2    3/ \  /4   5 6
    在这个最小堆中，每个父节点的值都小于其子节点的值。

3. 堆的数组表示

由于堆是完全二叉树，因此可以用数组来表示堆。这种表示方法不仅节省空间，还能方便地通过索引访问父节点和子节点。

数组表示规则
  • 对于一个节点 i（数组中的索引，从 0 开始）：
    • 父节点：(i - 1) / 2
    • 左子节点：2 * i + 1
    • 右子节点：2 * i + 2
示例

假设有一个数组 [10, 7, 8, 5, 6, 3]，它表示一个最大堆：

索引: 0  1  2  3  4  5
值:  10 7  8  5  6  3

对应的堆结构：

        10 (0)/    \7 (1)  8 (2)/ \     /5(3)6(4)3(5)
  • 验证父子节点关系：
    • 节点 1（值 7）的父节点是 (1 - 1) / 2 = 0（值 10）。
    • 节点 2（值 8）的父节点是 (2 - 1) / 2 = 0（值 10）。
    • 节点 0（值 10）的左子节点是 2 * 0 + 1 = 1（值 7），右子节点是 2 * 0 + 2 = 2（值 8）。

4. 堆排序的关键操作

堆排序的核心操作包括：

  1. 构建堆（Heapify）：

    • 将一个无序数组调整为一个最大堆或最小堆。
    • 从最后一个非叶子节点开始，逐步向上调整每个子树，使其满足堆的性质。

  2. 调整堆（Sift Down 或 Sift Up）：

    • Sift Down：从某个节点开始，向下调整子树，使其满足堆的性质。
    • Sift Up：从某个节点开始，向上调整子树，使其满足堆的性质。

  3. 排序：

    • 将堆顶元素与堆的最后一个元素交换，然后将堆的大小减一。
    • 对剩余的堆进行调整，使其重新满足堆的性质。
    • 重复上述步骤，直到堆的大小为 1。

二. 堆的构建（Heapify）

堆化（Heapify）是将一个无序数组调整为堆的过程。堆化的核心思想是从最后一个非叶子节点开始，逐步调整每个子树，使其满足堆的性质（最大堆或最小堆）。

堆化的步骤：
  1. 找到最后一个非叶子节点：
    • 最后一个非叶子节点的索引为 (n / 2) - 1，其中 n 是数组的长度。
  2. 从后向前调整：
    • 从最后一个非叶子节点开始，向前依次调整每个节点。
    • 对每个节点，检查其是否满足堆的性质。如果不满足，则向下调整（Sift Down）。
示例：

假设有一个数组 [4, 10, 3, 5, 1]，我们需要将其构建为最大堆：

  1. 最后一个非叶子节点的索引是 (5 // 2) - 1 = 1（值 10）。
  2. 从索引 1 开始向前调整：
    • 调整节点 1（值 10），其子树已经满足最大堆性质。
    • 调整节点 0（值 4），其左子节点 10 大于 4，交换两者。
    • 调整后的数组为 [10, 5, 3, 4, 1]。

2. 实现堆化操作

堆化操作可以通过递归或迭代实现。以下是最大堆的堆化实现（以 java为例）：

public class Heapify {// 堆化操作，将数组调整为最大堆public static void heapify(int[] arr, int n, int i) {int largest = i; // 初始化最大值为当前节点int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点存在且大于当前最大值if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点存在且大于当前最大值if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是当前节点，交换并递归堆化if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;// 递归堆化受影响的子树heapify(arr, n, largest);}}// 构建最大堆public static void buildMaxHeap(int[] arr) {int n = arr.length;// 从最后一个非叶子节点开始，向前遍历for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}}// 打印数组public static void printArray(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}public static void main(String[] args) {int[] arr = {4, 10, 3, 5, 1};System.out.println("原始数组:");printArray(arr);// 构建最大堆buildMaxHeap(arr);System.out.println("最大堆数组:");printArray(arr);}
}

3. 插入和删除操作

堆的插入和删除操作是堆数据结构的基本操作，分别通过“上浮”和“下沉”来维护堆的性质。

插入操作：
  1. 将新元素添加到堆的末尾。
  2. 对新元素进行“上浮”操作，使其满足堆的性质。
上浮（Sift Up）实现：
    /*** 插入操作（插入末尾），通过上浮（Sift Up）实现*/private static void siftUp(List<Integer> arr, int i) {while (i > 0) {// 父节点索引int parent = (i - 1) / 2;if(arr.get(parent) < arr.get(i)) {// 交换当前节点和父节点Integer temp = arr.get(parent);arr.set(parent, arr.get(i));arr.set(i, temp);// 继续上浮i = parent;}}}
删除操作：
  1. 删除堆顶元素（最大值或最小值）。
  2. 将堆的最后一个元素移到堆顶。
  3. 对堆顶元素进行“下沉”操作，使其满足堆的性质。
下沉（Sift Down）实现：
/*** 取出堆顶元素，并重新排序* @param arr* @return*/private static Integer getHeapUp(List<Integer> arr) {Integer heapUpNumber = arr.get(0);arr.set(0, arr.get(arr.size() - 1));arr.remove(arr.size() - 1);System.out.println("取出堆顶元素后的集合：");printArray(arr);siftDown(arr, arr.size(), 0);return heapUpNumber;}/***  下沉（Sift Down）实现*/private static void siftDown(List<Integer> arr, int length, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if(left < length && arr.get(left) > arr.get(largest)) {largest = left;}if(right < length && arr.get(right) > arr.get(largest)) {largest = right;}if(largest != i) {int swap = arr.get(i);arr.set(i, arr.get(largest));arr.set(largest, swap);siftDown(arr, length, largest);}}

三：实现堆排序

堆排序的核心思想是利用最大堆的性质，逐步将堆顶元素（最大值）取出并放到数组的末尾，最终得到一个有序数组:

  • 将堆顶元素（最大值）与堆的最后一个元素交换。
  • 将堆的大小减一（即排除已排序的部分）。
  • 对剩余的堆进行调整，使其重新满足最大堆的性质。
  • 重复上述步骤，直到堆的大小为 1。
import java.util.Arrays;public class HeapSort {/*** 将数组 arr 的索引 i 的子树调整为最大堆。** @param arr 待调整的数组* @param n   堆的大小* @param i   当前节点的索引*/private static void heapify(int[] arr, int n, int i) {int largest = i; // 假设当前节点是最大值int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点存在且大于当前节点if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点存在且大于当前节点if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是当前节点，交换并递归调整if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest); // 递归调整子树}}/*** 对数组 arr 进行堆排序。** @param arr 待排序的数组*/public static void heapSort(int[] arr) {int n = arr.length;// 1. 构建最大堆// 从最后一个非叶子节点开始，向前依次调整for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 2. 排序// 将堆顶元素（最大值）与堆的最后一个元素交换，然后调整剩余堆for (int i = n - 1; i > 0; i--) {// 交换堆顶和最后一个元素int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整剩余堆heapify(arr, i, 0);}}/*** 测试堆排序*/public static void testHeapSort() {// 测试用例int[][] testCases = {{4, 10, 3, 5, 1}, // 普通数组{1, 2, 3, 4, 5},  // 已经有序的数组{5, 4, 3, 2, 1},  // 逆序数组{},               // 空数组{1},             // 单个元素的数组{3, 3, 3, 3, 3}  // 所有元素相同的数组};for (int[] arr : testCases) {System.out.println("排序前: " + Arrays.toString(arr));heapSort(arr);System.out.println("排序后: " + Arrays.toString(arr));System.out.println("---------------------");}}/*** 性能测试*/public static void performanceTest() {int[] sizes = {1000, 10000, 100000}; // 不同规模的数组for (int size : sizes) {int[] arr = generateLargeArray(size);long startTime = System.currentTimeMillis();heapSort(arr);long endTime = System.currentTimeMillis();System.out.printf("数组大小: %d, 排序耗时: %d 毫秒\n", size, endTime - startTime);}}/*** 生成大规模随机数组** @param size 数组大小* @return 随机数组*/private static int[] generateLargeArray(int size) {int[] arr = new int[size];for (int i = 0; i < size; i++) {arr[i] = (int) (Math.random() * 100000);}return arr;}public static void main(String[] args) {// 测试堆排序testHeapSort();// 性能测试performanceTest();}
}
  1. 解决力扣（LeetCode）上的堆排序相关问题：
    • 215. 数组中的第K个最大元素
    • 912. 排序数组

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【网络编程】之TCP实现客户端远程控制服务器端及断线重连

【网络编程】之TCP实现客户端远程控制服务器端及断线重连

【网络编程】之TCP实现客户端远程控制服务器端及断线重连 TCP网络通信实现客户端简单远程控制主机基本功能演示通信过程代码实现服务器模块执行命令模块popen系列函数 客户端模块服务器主程序 windows作为客户端与服务器通信#pragma comment介绍 客户端使用状态机断线重连代码实…
阅读更多...
Git快速入门

Git快速入门

文章目录 Git简介准备工作常用的Linux命令git配置 git工作原理git项目创建和克隆git基本操作命令git忽略文件配置ssh远程连接 IDEA集成Gitgit分支&#xff08;多人开发&#xff09;公司中用到的&#xff08;很清楚&#xff09; Git 简介 Git就是版本控制的工具 下面这个叫手动…
阅读更多...
Redis 的几个热点知识

Redis 的几个热点知识

前言 Redis 是一款内存级的数据库&#xff0c;凭借其卓越的性能&#xff0c;几乎成为每位开发者的标配工具。 虽然 Redis 包含大量需要掌握的知识&#xff0c;但其中的热点知识并不多。今天&#xff0c;『知行』就和大家分享一些 Redis 中的热点知识。 Redis 数据结构 Redis…
阅读更多...
深入解析Java虚拟机（JVM）的核心组成

深入解析Java虚拟机（JVM）的核心组成

深入解析Java虚拟机&#xff08;JVM&#xff09;的核心组成 Java虚拟机&#xff08;JVM&#xff09;作为Java语言跨平台的核心实现&#xff0c;其架构设计精妙而复杂。理解JVM的组成部分&#xff0c;是掌握Java内存管理、性能调优和问题排查的关键。本文将从四大核心模块剖析J…
阅读更多...
GIT工具学习【2】：分支

GIT工具学习【2】：分支

1.什么是分支 新建一个分支&#xff0c;可以认为把当前项目copy了一份&#xff0c;不太严谨&#xff0c;没毛病&#xff0c;里面虽然文件内容和名字相同&#xff0c;其实互相没有关系。 2.什么是合并分支 就是把两个分支&#xff08;项目文件夹&#xff09;合并在一起 git m…
阅读更多...
40岁开始学Java：Java中单例模式（Singleton Pattern）,适用场景有哪些？

40岁开始学Java：Java中单例模式（Singleton Pattern）,适用场景有哪些？

在Java中&#xff0c;单例模式&#xff08;Singleton Pattern&#xff09;用于确保一个类只有一个实例&#xff0c;并提供全局访问点。以下是详细的实现方式、适用场景及注意事项&#xff1a; 一、单例模式的实现方式 1. 饿汉式&#xff08;Eager Initialization&#xff09; …
阅读更多...
Linux常见基本指令（一）

Linux常见基本指令（一）

目录 前言 1、ls指令 2、用户相关指令 3、pwd指令 4、cd指令 相对路径与绝对路径 5、创建、删除文件和目录相关的指令 创建相关的指令 删除相关的指令 6、拷贝、移动和重命名 cp指令 mv指令 前言 学习Linux的过程中一定要多自己动手&#xff0c;Linux的指令繁多&a…
阅读更多...
测试金蝶云的OpenAPI

测试金蝶云的OpenAPI

如何使用Postman测试K3Cloud的OpenAPI 1. 引言 在本篇博客中&#xff0c;我将带你逐步了解如何使用Postman测试和使用K3Cloud的OpenAPI。内容包括下载所需的SDK文件、配置文件、API调用及测试等步骤。让我们开始吧&#xff01; 2. 下载所需的SDK文件 2.1 获取SDK 首先&…
阅读更多...
Tomcat

Tomcat

1.Tomcat是什么&#xff1f; Tomcat 是一个开源的、轻量级的 Servlet 容器&#xff0c;也被称为 Web 服务器&#xff0c;由 Apache 软件基金会的 Jakarta 项目开发&#xff0c;在 Java Web 开发领域应用广泛。 1&#xff09;Servlet 容器&#xff1a;Servlet 是 Java 语言编写…
阅读更多...
【windows driver】 开发环境简明安装教程

【windows driver】 开发环境简明安装教程

一、下载路径 https://learn.microsoft.com/en-us/windows-hardware/drivers/other-wdk-downloads 二、安装步骤&#xff1a; 1、安装Visual Studio IDE 笔者建议安装最新版本&#xff0c;可以向下兼容。发文截止到目前&#xff0c;VS2022是首选&#xff0c;当前笔者由于项…
阅读更多...
长时间目标跟踪算法(3)-GlobalTrack：A Simple and Strong Baseline for Long-termTracking

长时间目标跟踪算法(3)-GlobalTrack：A Simple and Strong Baseline for Long-termTracking

GlobalTrack的原始论文和源码均已开源&#xff0c;下载地址。 目录 背景与概述 1.1 长期视觉跟踪的挑战 1.2 现有方法的局限性 1.3 GlobalTrack的核心思想 算法原理与架构 2.1 全局实例搜索框架 2.2 Query-Guided RPN&#xff08;QG-RPN&#xff09; 2.3 Query-Guided RCNN&a…
阅读更多...
使用mermaid查看cursor程序生成的流程图

使用mermaid查看cursor程序生成的流程图

一、得到cursor生成的流程图文本 cursor写的程序正常运行后&#xff0c;在对话框输入框中输入诸如“请生成扫雷的代码流程图”&#xff0c;然后cursor就把流程图给生成了&#xff0c;但是看到的还是文本的样子&#xff0c;保留这部分内容待用 二、注册一个Mermaid绘图账号 …
阅读更多...
MacOS本地部署Deepseek，不联网也可以使用AI，保护隐私

MacOS本地部署Deepseek，不联网也可以使用AI，保护隐私

苹果笔记本本地部署deepseek主要用到Ollama与open-webui 1. 安装Ollama “Ollama” 是一个轻量级的 AI 模型运行时环境&#xff08;runtime&#xff09;&#xff0c;旨在简化在本地部署和使用大语言模型&#xff08;LLM&#xff09;的过程。它由 Vicarious 公司开发&#xff…
阅读更多...
unity学习62，尝试做第一个小游戏项目：flappy bird

unity学习62，尝试做第一个小游戏项目：flappy bird

目录 学习参考 1 创建1个unity 2D项目 1.1 2D项目模板选择 1.1.1 2D(built-in-Render pipeline) 1.1.2 universe 2D 1.1.3 这次选择 2D(built-in-Render pipeline) 1.2 创建项目 1.2.1 注意点 1.2.2 如果想修改项目名 2 导入美术资源包 2.1 下载一个flappy bird的…
阅读更多...
基于Matlab的多目标粒子群优化

基于Matlab的多目标粒子群优化

在复杂系统的设计、决策与优化问题中&#xff0c;常常需要同时兼顾多个相互冲突的目标&#xff0c;多目标粒子群优化&#xff08;MOPSO&#xff09;算法应运而生&#xff0c;作为群体智能优化算法家族中的重要成员&#xff0c;它为解决此类棘手难题提供了高效且富有创新性的解决…
阅读更多...
使用DiskGenius工具来实现物理机多硬盘虚拟化迁移

使用DiskGenius工具来实现物理机多硬盘虚拟化迁移

使用DiskGenius工具来实现物理机多硬盘虚拟化迁移 概述准备工作注意事项实操过程记录1、Win7虚拟机&#xff0c;安装有两个硬盘&#xff08;硬盘0和硬盘1&#xff09;&#xff0c;各分了一个区&#xff0c;磁盘2是一块未使用的磁盘2、运行DiskGenius程序&#xff0c;记录现有各…
阅读更多...
win本地vscode通过代理远程链接linux服务器

win本地vscode通过代理远程链接linux服务器

时间&#xff1a;2025.2.28 1. win本地下载nmap.exe nmap官网 https://nmap.org/或者 https://nmap.org/download#windows下载win版本并安装。 2. vscode插件Remote-SSH 插件下载Remote-SSH 3. 配置 按照图中顺序配置ssh 1.点击左侧工具栏的“小电视”图标 2.点击ssh的…
阅读更多...
yolo初体验

yolo初体验

看别人说的好简单,3行代码完成yolo11: from ultralytics import YOLO model YOLO("yolo11x.pt")##第一次运行自动下载 model.predict(source"0",showTrue) 当然代码没错:但是环境不好配: 首先:pip install ultralytics 会主动下载依赖 pytorch pandas-…
阅读更多...
TCP 连接故障排查与 SYN 洪泛攻击防御

TCP 连接故障排查与 SYN 洪泛攻击防御

1 SYN 洪泛攻击防御 1.1 SYN Flood是什么&#xff1f; SYN Flood是互联网上最原始、最经典的DDoS&#xff08;Distributed Denial of Service&#xff0c;分布式拒绝服务&#xff09;攻击之一&#xff0c;旨在耗尽可用服务器资源&#xff0c;致使服务器无法传输合法流量。 SYN…
阅读更多...
ArcGIS Pro应用指南：如何为栅格图精确添加坐标信息

ArcGIS Pro应用指南：如何为栅格图精确添加坐标信息

一、引言 在地理信息系统中&#xff0c;栅格图是一种重要的数据类型。 然而&#xff0c;有时我们从网络上获取的栅格图并不包含坐标信息&#xff0c;这使得它们难以与其他带有坐标信息的数据进行集成和分析。 为了解决这一问题&#xff0c;我们需要对栅格图进行地理配准&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023