堆排序算法及实现

古城微笑少年丶 2022-03-08 20:58 201阅读 0赞

使用数组来模拟堆。  
由于是一个满二叉树  
左孩子使用nums\[2i+1\]模拟  
右孩子使用nums\[2i+2\]模拟

堆排序的基本思路为：  
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;  
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;  
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

--------------------

# 1. 堆调整函数 #

#始终保持nums[i] > nums[2i+1] and nums[i] > nums[2i+2]
    def heapify(nums, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and nums[l] > nums[largest]:
            largest = l
        if r < n and nums[r] > nums[largest]:
            largest = r
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            heapify(nums, n, largest)

--------------------

# 2.堆排序函数 #

def heapSort(nums):
        i = len(nums) // 2
        #建立堆，使得nums[i] > nums[2i+1] and nums[i] > nums[2i+2]
        while i >= 0:
            heapify(nums, len(nums), i)
            i -= 1
        for i in range(len(nums) - 1, -1, -1):
            nums[0], nums[i] = nums[i], nums[0]
            #最大的换到末尾，然后对换到0的数字继续构造堆，这个时候末尾的元素就不考虑了
            heapify(nums, i, 0)

因为nums\[0\]的元素始终是最大的，nums\[0\] > nums\[1 or 2\] 而nums\[1\] > nums\[3 or 4\]以此类推和递归  
所以每次只需要将0后沉，然后从0的位置开始调整堆即可。

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关 php实现数据排序算法,PHP实现排序堆排序算法

这篇文章主要为大家详细介绍了PHP实现排序堆排序(Heap Sort)算法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下算法引进：在这里我直接引用《大话数据结构》里

素颜马尾好姑娘i/ 2023年01月15日 02:18/ 0 赞/ 118 阅读

相关【排序算法】堆排序原理及Java实现

1、基本思想堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根结点的值小于（或大于）两个子节点的值，同时，根节点的两个子树也分别是一

蔚落/ 2022年08月21日 10:54/ 0 赞/ 233 阅读

相关 Java实现堆排序算法

这里列出自己写的两个堆排序算法，第一个是之前写的，当时不知道堆调整的思想，第二个是优化堆调整后的方法。这是第一个：之前只知道如何建堆，不知道算法导论上还有如此巧

淡淡的烟草味﹌/ 2022年07月21日 00:16/ 0 赞/ 171 阅读

相关 php实现堆排序算法

最近在准备各种面试，复习了一波算法基础，关于什么是堆排序我就不多说了，这里说的很详细，不明白的可以参考一下： https://jingyan.baidu.com/articl

╰半夏微凉°/ 2022年06月04日 10:09/ 0 赞/ 190 阅读

相关堆排序原理及算法实现

堆排序堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。 1.堆堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key\[i\]<=key\[2i+

傷城~/ 2022年06月02日 11:47/ 0 赞/ 197 阅读

相关排序算法：堆排序算法实现及分析

堆排序介绍堆排序（Heap Sort）就来利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。

Myth丶恋晨/ 2022年05月31日 11:45/ 0 赞/ 267 阅读

相关排序算法之堆排序及Java实现

一、排序算法的分类 1. 选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]） 2. 交换排序（[冒泡排序][Link 3]，[快速排序][Lin

傷城~/ 2022年05月26日 04:47/ 0 赞/ 232 阅读

相关堆排序算法实现

堆排序:结构逻辑上是完全二叉树,但是可以使用顺序存储来实现一些二叉树的区别: 二叉树:度数最大为2并且每个子树也是二叉树满二叉树:每层节点都是满的,没有空缺,也就是,

冷不防/ 2022年03月10日 08:40/ 0 赞/ 217 阅读

相关堆排序算法及实现

使用数组来模拟堆。由于是一个满二叉树左孩子使用nums\[2i+1\]模拟右孩子使用nums\[2i+2\]模拟堆排序的基本思路为： a.将无需序列构

古城微笑少年丶/ 2022年03月08日 20:58/ 0 赞/ 202 阅读

相关堆排序算法（C#实现）

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。另一种是垃圾收集存储

ゝ一世哀愁。/ 2021年11月26日 16:56/ 0 赞/ 255 阅读