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

每日一题——小根堆实现堆排序算法

news 来源：原创 2025/5/16 2:09:15

小根堆实现堆排序算法

- 堆排序的基本思想
- - 堆排序的步骤
- 实现步骤
- - 1. 构建小根堆
  - 2. 删除最小元素并调整堆
- C语言实现
- 输出示例
- 代码解释
- - 1. percolateDown 函数
  - 2. buildMinHeap 函数
  - 3. heapSort 函数
  - 4. printArray函数
- 排序过程详解
- - 步骤1：构建小根堆
  - 步骤2：删除堆顶元素并调整堆
  - 最终结果
- 总结

堆排序是一种基于堆数据结构的排序算法，利用堆的性质来高效地对数组进行排序。堆排序的时间复杂度为

O(n\log n)

，而且是一种原地排序算法，空间复杂度为

O (1)

。

堆排序的基本思想

堆排序的核心思想是利用小根堆的性质，将数组构建成一个小根堆，然后逐步删除堆顶元素（最小值），并将其放到数组的末尾。通过重复这个过程，数组最终会被排序。

堆排序的步骤

构建小根堆：将数组构建成一个小根堆。
删除最小元素：每次删除堆顶元素（最小值），并将堆的最后一个元素移到堆顶，然后调整堆以保持小根堆的性质。
重复步骤2：直到堆为空，此时数组已经被排序。

实现步骤

1. 构建小根堆

从最后一个非叶子节点开始，逐个向下调整，直到根节点。最后一个非叶子节点的索引为 $ \left\lfloor \frac{2n - 2}{2} \right\rfloor $，其中 $n$ 是数组的长度。

2. 删除最小元素并调整堆

每次删除堆顶元素，将其放到数组的末尾，然后将堆的最后一个元素移到堆顶，再进行向下调整。

C语言实现

#include <stdio.h>
#include <stdlib.h>// 向下调整堆
void percolateDown(int* arr, int n, int i) {int smallest = i; // 当前节点索引int left = 2 * i + 1; // 左子节点索引int right = 2 * i + 2; // 右子节点索引//找到父子结点中的最小节点索引// 如果左子节点存在且小于当前节点的值if (left < n && arr[left] < arr[smallest]) smallest = left;// 如果右子节点存在且小于当前最小值if (right < n && arr[right] < arr[smallest])smallest = right;// 如果最小值不是当前节点，交换并继续调整堆if (smallest != i) {int temp = arr[i];arr[i] = arr[smallest];arr[smallest] = temp;percolateDown(arr, n, smallest);  // 递归调整}
}// 构建小根堆
void buildMinHeap(int* arr, int n) {// 从最后一个**非叶子节点**开始调整后一大半都是叶子节点for (int i = (n - 2) / 2; i >= 0; i--) {percolateDown(arr, n, i);}
}// 堆排序
void heapSort(int* arr, int n) {// 构建小根堆buildMinHeap(arr, n);// 逐个删除最小元素并调整堆for (int i = n - 1; i >= 0; i--) {// 将堆顶元素（最小值）放到数组末尾int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整剩余的堆percolateDown(arr, i, 0);}
}// 打印数组
void printArray(int* arr, int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {3, 1, 6, 5, 2, 4}; // 待排序数组int n = sizeof(arr) / sizeof(arr[0]);printf("Original array: ");printArray(arr, n);heapSort(arr, n);  // 执行堆排序printf("Sorted array: ");printArray(arr, n);  // 输出排序后的数组return 0;
}

输出示例

运行上述代码，输出如下：

Original array: 3 1 6 5 2 4 
Sorted array: 1 2 3 4 5 6

代码解释

1. percolateDown 函数

这个函数用于向下调整堆，确保当前节点的值小于其子节点的值。通过比较当前节点、左子节点和右子节点的值，找到最小值的索引。如果最小值不是当前节点，交换它们，并递归调整子树。

2. buildMinHeap 函数

从最后一个非叶子节点开始，逐个向下调整，直到根节点。最后一个非叶子节点的索引为 $\left\lfloor \frac{2n - 2}{2} \right\rfloor$ 。

3. heapSort 函数

首先调用 buildMinHeap 构建小根堆。然后逐个删除堆顶元素（最小值），将其放到数组末尾。每次删除后，调整剩余的堆，确保堆的性质仍然成立。

4. printArray函数

该函数用于打印数组，方便查看排序结果。

排序过程详解

假设我们有一个数组 arr[] = {3, 1, 6, 5, 2, 4}，以下是堆排序的详细过程：

步骤1：构建小根堆

构建小根堆：从最后一个非叶子节点开始向下调整，直到根节点。
- arr[] = {3, 1, 6, 5, 2, 4}
- 从索引 2（值为 6）开始：
  - 左子节点 5，右子节点 4，最小值为 4，交换 6 和 4，调整得到 arr[] = {3, 1, 4, 5, 2, 6}。
- 继续调整索引 1（值为 1）：
  - 左子节点 5，右子节点 2，最小值为 2，交换 1 和 2，调整得到 arr[] = {3, 2, 4, 5, 1, 6}。
- 最后调整索引 0（值为 3）：
  - 左子节点 2，右子节点 4，最小值为 2，交换 3 和 2，调整得到 arr[] = {2, 3, 4, 5, 1, 6}。
  - 接着，索引 1 的值为 3，继续向下调整，最终得到 arr[] = {2, 1, 4, 5, 3, 6}。

此时，堆构建完成。

步骤2：删除堆顶元素并调整堆

删除堆顶元素并调整堆：
- 第一次：
  - 删除堆顶元素 2，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 1, 4, 5, 3}。
  - 调整堆，交换 6 和 1，然后交换 6 和 3，得到 arr[] = {1, 3, 4, 5, 6}。
- 第二次：
  - 删除堆顶元素 1，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 3, 4, 5}。
  - 调整堆，交换 6 和 3，得到 arr[] = {3, 6, 4, 5}，然后交换 6 和 5，得到 arr[] = {3, 5, 4, 6}。
- 第三次：
  - 删除堆顶元素 3，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 5, 4}。
  - 调整堆，交换 6 和 4，得到 arr[] = {4, 5, 6}。
- 第四次：
  - 删除堆顶元素 4，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 5}。
  - 调整堆，交换 6 和 5，得到 `arr[] =

{5, 6}`。

第五次：
- 删除堆顶元素 5，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6}。
- 此时，堆中只剩一个元素，排序完成。

最终结果

排序后的数组为 arr[] = {1, 2, 3, 4, 5, 6}。

总结

堆排序利用小根堆的性质，通过构建堆、删除堆顶元素并调整堆的方式进行排序。它的时间复杂度为 $O(n\log n)$ ，空间复杂度为 $O (1)$ ，是一种原地排序算法，不稳定排序适用于大规模数据的排序任务。

每日一题——小根堆实现堆排序算法

小根堆实现堆排序算法堆排序的基本思想堆排序的步骤实现步骤1. 构建小根堆2. 删除最小元素并调整堆 C语言实现输出示例代码解释1. percolateDown 函数2. buildMinHeap 函数3. heapSort 函数4. printArray函数排序过程详解步骤1：构建小根堆步骤2：删除堆…...

编程日记 2025/5/16 2:09:15

k8s集群

文章目录项目描述项目环境系统与软件版本概览项目步骤环境准备IP地址规划关闭selinux和firewall配置静态ip地址修改主机名添加hosts解析项目步骤一、使用kubeadm安装k8s单master的集群环境（1个master2个node节点）1、互相之间建立免密通道2.关闭交换分…...

编程日记 2025/5/14 11:02:22

数据分析系列--[11] RapidMiner,K-Means聚类分析(含数据集)

一、数据集二、导入数据三、K-Means聚类数据说明:提供一组数据,含体重、胆固醇、性别。分析目标:找到这组数据中需要治疗的群体供后续使用。一、数据集点击下载数据集二、导入数据三、K-Means聚类 Ending, congratulations, youre done....

编程日记 2025/5/16 1:46:28

技术架构师成长路线（2025版）

目录通用知识计算机原理（1 - 2 个月） 数据结构（2 - 3 个月） 网络编程（1 - 2 个月） 软件工程（1 个月） 基础知识 Java 编程语言基础（2 - 3 个月） JVM&…...

编程日记 2025/5/7 9:07:26

NetLify账号无法登录解决办法

本文收录在【建站】专栏内，专栏目录：【建站】专栏目录用github账号登录时，说校验失败 Authentication Error Authenticating failed due to the following error: Your account requires additional verification. Please check your email…...

编程日记 2025/5/14 6:59:56

linux本地部署deepseek-R1模型

国产开源大模型追平甚至超越了CloseAI的o1模型，大国崛起时刻！！！ DeepSeek R1 本地部署指南在人工智能技术飞速发展的今天，本地部署AI模型成为越来越多开发者和企业关注的焦点。本文将详细介绍如何在本地部署DeepS…...

编程日记 2025/5/12 8:49:35

集合通讯概览

集合通信概览 （1）通信的算法是根据通讯的链路组成的 （2）因为通信链路跟硬件强相关，所以每个CCL的库都不一样芯片与芯片、不同U之间是怎么通信的多卡训练：多维并行（xxx并行在上一期已经讲述…...

编程日记 2025/5/15 11:02:27

如何解决云台重力补偿？

如何解决云台重力补偿？最近在调试步兵云台的时候，由于枪管、图传、摄像头等重力的原因，pitch轴的参数尤其难以调整，又不想抬升和降低使用两套不同的参数，所以使用了重力补偿，效果也是比较理想的，于是整理为一篇文章记录一下一、问题根源：枪管重力在“搞事情” 想象…...

编程日记 2025/5/15 1:01:55

【LeetCode 刷题】回溯算法(4)-排列问题

此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法排列问题相关的题目解析。文章目录 46.全排列47.全排列 II 46.全排列题目链接 class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res, path [], []used [0] * len(n…...

编程日记 2025/5/14 23:50:38

FPGA|IP核PLL调用测试：建立工程

闲来无事，测试下FPGA的IP核调用一、生成工程 1、打开软件新建工程 2、命名为PLL_test 3、选择芯片型号 4、生成工程如图...

编程日记 2025/4/27 14:03:23

数据的表示和运算

一-定点数的表示 1-定点数和浮点数定点数：小数点的位置固定（常规计数） 浮点数：小数点的位置不固定（科学计数法） 2-定点数的表示 ①无符号数整个机器字长的全部二进制位均为数值位，没有符号…...

编程日记 2025/5/13 1:51:27

22.Word：小张-经费联审核结算单❗【16】

目录 NO1.2 NO3.4 NO5.6.7 NO8邮件合并 MS搜狗输入法 NO1.2 用ms打开文件，而不是wps❗不然后面都没分布局→页面设置→页面大小→页面方向→上下左右：页边距→页码范围：多页：拼页光标处于→布局→分隔符：分节符…...

编程日记 2025/5/16 2:00:32

鲸鱼算法 matlab pso

算法原理鲸鱼优化算法的核心思想是通过模拟座头鲸的捕食过程来进行搜索和优化。座头鲸在捕猎时会围绕猎物游动并产生气泡网，迫使猎物聚集。这一行为被用来设计搜索策略，使算法能够有效地找到全局最优解。算法步骤 ‌初始化‌：随机生成一…...

编程日记 2025/5/9 18:06:37

c++之模板进阶

在前面的文章中，我们已经简单的了解了模板的使用，在这篇文章中，我们将继续深入探讨模板 1.模板的特化 1.1 概念通常情况下，使用模板可以实现一些与类型无关的代码，但对于一些特殊类型的可能会得到一些错误的结果&a…...

编程日记 2025/5/13 2:25:51

C语言中的信号量

信号是操作系统中用来传递特定消息的机制。操作系统可以使用这种方式将程序运行过程中发生的各类特殊情况发送给程序，并按照其指定的逻辑进行处理。信号名称都以 “SIG” 作为前缀，如程序访问非法内存时，会产生名为 SIGSEGV 的信号。程序需…...

编程日记 2025/5/15 5:27:57

AI主流大模型介绍和API价格比较

主流的大模型系列 ###1. OpenAI: GPT-4，GPT-4 Turbo， GPT-4o OpenAI 的介绍： 全称：Open Artificial Intelligence，简称OpenAI。性质：起初为非营利性组织，后转变为由营利性公司OpenAI LP及非营…...

编程日记 2025/5/14 17:13:33

自主Shell命令行解释器

什么是命令行我们一直使用的"ls","cd","pwd","mkdir"等命令，都是在命令行上输入的，我们之前对于命令行的理解： 命令行是干啥的？是为我们做命令行解释的。命令行这个东西实际上是我们…...

编程日记 2025/5/12 15:16:24

git笔记-简单入门

git笔记 git是一个分布式版本控制系统，它的优点有哪些呢？分为以下几个部分与集中式的版本控制系统比起来，不用担心单点故障问题，只需要互相同步一下进度即可。支持离线编辑，每一个人都有一个完整的版本库。跨平台支持…...

编程日记 2025/5/15 2:00:32

重新刷题求职2-DAY1

DAY1 1.704. 二分查找给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。最普通的二分查找，查用的习惯左闭右…...

编程日记 2025/5/15 16:01:15

浅析DDOS攻击及防御策略

DDoS（分布式拒绝服务）攻击是一种通过大量计算机或网络僵尸主机对目标服务器发起大量无效或高流量请求，耗尽其资源，从而导致服务中断的网络攻击方式。这种攻击方式利用了分布式系统的特性，使攻击规模更大、影响范围更广…...

编程日记 2025/5/14 21:39:24

路径规划之启发式算法之二十九：鸽群算法（Pigeon-inspired Optimization, PIO）

鸽群算法（Pigeon-inspired Optimization, PIO）是一种基于自然界中鸽子群体行为的智能优化算法，由Duan等人于2014年提出。该算法模拟了鸽子在飞行过程中利用地标、太阳和磁场等导航机制的行为，具有简单、高效和易于实现的特点，适用于解决连续优化问题。更多的仿生群体算法…...

编程日记 2025/5/13 5:38:16

SwiftUI 在 Xcode 预览修改视图 FetchedResults 对象的属性时为什么会崩溃？

概览从 SwiftUI 诞生那天起，让秃头码农们又爱又恨的 Xcode 预览就在界面调试中扮演了及其重要的角色。不过，就是这位撸码中的绝对主角却尝尝在关键时刻“掉链子”。比如当修改 SwiftUI 视图中 FetchedResults 对象的属性时，Xcode 预览可能…...

编程日记 2025/5/12 12:54:12

pytorch实现基于Word2Vec的词嵌入

PyTorch 实现 Word2Vec（Skip-gram 模型） 的完整代码，使用中文语料进行训练，包括数据预处理、模型定义、训练和测试。 1. 主要特点支持中文数据，基于 jieba 进行分词使用 Skip-gram 进行训练，适用于小数…...

编程日记 2025/5/9 11:31:27

MVC 文件夹：架构之美与实际应用

MVC 文件夹：架构之美与实际应用引言 MVC（Model-View-Controller）是一种设计模式，它将应用程序分为三个核心组件：模型（Model）、视图（View）和控制器（Controller）。这种架构模式不仅提高了代码的可维护性和可扩展性，而且使得开发流程更加清晰。本文将深入探讨MVC文…...

编程日记 2025/5/15 13:48:17

from flask import Flask, render_template, request, jsonify import sys from io import StringIO import contextlib import subprocess import importlib import threading import time import ast import reapp Flask(__name__)RESTRICTED_PACKAGES {tkinter: 抱歉&…...

编程日记 2025/5/15 8:50:47