使用最小堆进行降序的堆排序

冬明大大_4553

冬明大大_4553

2023-08-29

869人浏览

转载

使用最小堆进行降序的堆排序

堆排序 - 堆排序是一种基于比较的算法,它使用二叉树数据结构按升序或降序对数字列表进行排序。它通过堆排序创建一个堆数据结构,其中根是最小元素,然后删除根,再次排序在根位置给出列表中第二小的数字。

最小堆 - 最小堆是一种数据结构,其中父节点始终小于子节点,因此根节点是所有元素中最小的元素。

问题陈述

给定一个整数数组。使用最小堆按降序对它们进行排序。

示例 1

Input: [2, 5, 1, 7, 0]
Output: [7, 5, 2, 1, 0]

示例 2

Input: [55, 1, 23, 10, 1]
Output: [55, 23, 10, 1, 1]

方法 1

为了使用最小堆按降序执行堆排序,我们创建一个元素的最小堆,并一次提取一个元素,通过反转顺序得到一个按降序排列的数组。

伪代码

procedure heapSort (arr[], n)
   Initialize priority queue: minHeap
   for i = 1 to n
      add arr[i] to minHeap
   i = n - 1
   while minHeap is not empty
      arr[i–] = top element of minHeap
      Remove the top element of minHeap
end procedure

示例:C++ 实现

在下面的程序中,我们使用最小堆对数组进行排序,然后反转顺序以获得结果。

#include <bits>
using namespace std;
// Function to heap sort in decreasing order using min heap
void heapSort(int arr[], int n){

   // Creating min heap using a priority queue
   priority_queue<int vector>, greater<int> > minHeap;
   
   // Inserting input array to min heap
   for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Sorted array : 9 6 5 5 2 1

时间复杂度 - O(nlogn)

空间复杂度 - O(n)

Jounce
Jounce

Jounce是一款AI文本写作工具,无限制免费AI文案写作。

下载

方法2

该问题的另一个解决方案是从最后一个非叶根模式开始并向后构建一个最小堆。然后我们可以通过交换根节点和最后一个叶子节点来对数组进行排序,然后恢复最小堆属性。

伪代码

procedure heapify (arr[], n , i)
   smallest = i
   l = 2i + 1
   r = 2i + 2
   if l <h3>示例:C++ 实现</h3><p>在下面的程序中,我们使用 heapify() 函数恢复以索引 i 为根的子树的最小堆属性,并使用 heapSort() 以相反的顺序构建最小堆。</p><pre class="brush:cpp;toolbar:false;">#include <bits>
using namespace std;

// Restores the min heap property of subtree rooted at index i
void heapify(int arr[], int n, int i){
   int smallest = i;
   int l = 2 * i + 1;
   int r = 2 * i + 2;
   if (l = 0; i--){
      heapify(arr, n, i);
   }
   
   // Sort the array by repeatedly swapping the root node with the last leaf node
   for (int i = n - 1; i >= 0; i--){
      swap(arr[0], arr[i]);
      heapify(arr, i, 0);
   }
}
int main(){
   int arr[6] = {5, 2, 9, 1, 5, 6};
   int n = 6;
   heapSort(arr, n);
   cout <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Sorted array : 9 6 5 5 2 1

使用之前使用 heapSort() 函数创建最小堆的方法,我们可以在这个解决方案中使用相同的方法,但不是使用 heapify 来恢复最小堆的属性,而是使用传统的 hep 排序算法来创建 amin堆和排序元素的顺序递增,并进一步反转以获得所需的输出。

伪代码

procedure heapSort (arr[], n)
   for i = n/2 - 1 to 0
   parent = i
      while parent *2+1 arr[child+1]
            child = child + 1
         end if
         if arr[parent] > arr[child]
            swap arr[parent] to arr[child]
            parent = child
         else
            break
         end if
   for i = n-1 to 0
      swap arr[0] to arr[i]
      parent = 0
      while parent*2+1 arr[child+1]
            child = child + 1
         end if
         if arr[parent] > arr[child]
            swap arr[parent] to arr[child]
            parent = child
         else
            break
         end if
end procedure

示例:C++ 实现

在下面的程序中,我们修改堆排序算法以降序对数组进行排序。

#include <bits>
using namespace std;

void heapSort(int arr[], int n){
   // Building min heap in reverse order
   for (int i = n / 2 - 1; i >= 0; i--) {
   
      // Starting from last parent node, apply heapify operation
      int parent = i;
      while (parent * 2 + 1  arr[child + 1]){
            child++;
         }
         if (arr[parent] > arr[child]){
            swap(arr[parent], arr[child]);
            parent = child;
         }
         else{
            break;
         }
      }
   }
   
   // Extarct elekemnhts form min heap in decreasing order
   for (int i = n - 1; i > 0; i--){
      swap(arr[0], arr[i]);
      int parent = 0;
      
      // Perform heapify operation at new root node
      while (parent * 2 + 1  arr[child + 1]){
            child++;
         }
         if (arr[parent] > arr[child]){
            swap(arr[parent], arr[child]);
            parent = child;
         }
         else {
            break;
         }
      }
   }
}
int main(){
   int arr[6] = {5, 2, 9, 1, 5, 6};
   int n = 6;
   heapSort(arr, n);
   cout <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Sorted array : 9 6 5 5 2 1

结论

总之,为了使用最小堆执行降序堆排序,我们可以使用多种方法,其中一些方法的时间复杂度为 O(nlogn),每种方法的空间复杂度各不相同。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2941

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

2023.07.18

7127

5

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

2023.08.10

2928

6

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习