算法之堆排序

简介: 本文介绍了堆排序算法的原理和实现,通过构建最大堆或最小堆,利用堆的性质进行高效的排序,并提供了具体的编程实现细节和示例。

堆排序是一种基于比较的排序算法,通过构建二叉堆(Binary Heap),可以利用堆的性质进行高效的排序。二叉堆是一个完全二叉树,可以有最大堆和最小堆两种形式。在最大堆中,父节点的值总是大于或等于其子节点的值;在最小堆中,父节点的值总是小于或等于其子节点的值。

先了解原理

在最大堆中,每次操作都会选出当前堆中的最大元素。这个元素被放置到堆的顶部,然后与数组的最后一个元素交换位置。交换后,该元素从堆中移除,因为它已经被放置在其最终位置。接下来,我们重新调整剩余的堆结构,以确保堆的最大元素位于顶部,为下一次操作做准备。通过不断重复这个过程,我们能够逐步构建出一个有序的数组。同理,小堆也是一样的

当然实际编程的时候要考虑式子

R[V]>=R[2V] , R[V]>=R[2V+1]

咱们话不多说直接看题吧。

看题的时候先思考参数,v代表什么,n代表什么?v是根节点编号,n是堆的元素数。

i=v,都是根节点编号,R[0]=R[i],就是将根节点存到R[0]。根据式子R[V]>=R[2V] , R[V]>=R[2V+1]

所以可以知道j=2*i 是出于什么目的了吧。

然后就是if判断j<=n应该很容易理解吧,因为n是总的堆的数目,j肯定要小于或者等于n的

至于那个if(j<n&&R[j]<R[j+1]) j++

这个很好理解,就是简单的将下面节点最大的用j表示,怎么说呢,就是你想想一颗二叉树,左节点是3,而右节点是4,而大堆肯定是选大的和根节点比较。所以才有这个if判断,如果右节点大,就让这个j++,让它指向右节点

然后就是那个空,明显是R[j] >=R[0] ,因为前面已经将R[0]=R[i],所以这里和R[0]进行比较就行了。

然后第二个空,肯定是构建大堆呗,Heapify(R,i,n),第三个空 i>1或i>=2,第四个空是R[1]=R[0]。

目录
相关文章
|
6月前
|
算法 Python
数据结构算法--4堆排序
堆排序过程概述:建立大根堆,将堆顶最大元素移出并替换为末尾元素,调整保持堆性质,重复此过程直至堆为空,实现排序。时间复杂度为O(nlogn)。Python中可用heapq模块进行堆操作。
|
7月前
|
机器学习/深度学习 人工智能 算法
数据结构与算法:堆排序和TOP-K问题
朋友们大家好,本节内容来到堆的应用:堆排序和topk问题
数据结构与算法:堆排序和TOP-K问题
|
7月前
|
存储 人工智能 算法
深入浅出堆排序: 高效算法背后的原理与性能
深入浅出堆排序: 高效算法背后的原理与性能
123 1
|
2月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
75 0
数据结构与算法学习十八:堆排序
|
2月前
|
算法 Java Go
深入了解堆排序算法
深入了解堆排序算法
32 1
|
7月前
|
移动开发 算法 前端开发
前端算法之堆排序
前端算法之堆排序
42 1
|
6月前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
50 3
|
6月前
|
搜索推荐 算法
【C/排序算法】:堆排序和选择排序
【C/排序算法】:堆排序和选择排序
40 0
|
6月前
|
存储 算法 C语言
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
40 0
|
7月前
|
人工智能 搜索推荐 算法
sort-04-heap sort 堆排序算法详解
这是一个关于排序算法的系列文章摘要,包括了10篇关于不同排序算法的链接,如冒泡排序、快速排序、选择排序、堆排序等。堆排序是一种基于比较的排序算法,利用了近似完全二叉树的结构并满足最大堆或最小堆的性质。最大堆中,每个节点的值都大于或等于其子节点。文章详细解释了最大堆的概念、节点访问方式以及堆的操作,包括堆调整和堆排序的过程,并通过图解展示了堆排序的具体步骤。此外,还提供了一个Java实现的堆排序代码示例。整个排序系列来源于一个开源项目,读者可以通过链接查看完整内容。
sort-04-heap sort 堆排序算法详解