python 堆排序

genedna 发布于2019-07-31 11:18 / 2171人阅读

摘要：堆排序堆排序是指利用堆这种数据结构所设计的一种排序算法。堆排序可以说是一种利用堆的概念来排序的选择排序。代码实现构建堆由下往上构建所以用每次踢掉求出的最大值

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点（但是不保证所有左子树比右子树小反之亦然）。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

算法步骤

创建一个堆 H[0……n-1]；（**对非叶子节点的子节点进行调节，构建堆**）

把堆首（最大值）和堆尾互换；

把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

Python 代码实现

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):#构建堆由下往上构建所以用-1
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left < arrLen and arr[left] > arr[largest]:
        largest = left
    if right < arrLen and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1 #每次踢掉求出的最大值
        heapify(arr, 0)
    return arr

GPU云服务器云服务器 python的堆排序堆排序用python 堆排序堆排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44979.html

八大排序算法的Python实现

摘要：是稳定的排序方法。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。算法实现选择排序堆排序描述堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法，它是选择排序的一种。 1、插入排序描述插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定...

princekin 2019-07-24 18:09 评论0 收藏0
Python 的 heapq 模块源码分析

摘要：原文链接起步模块实现了适用于列表的最小堆排序算法。本文内容将分为三个部分，第一个部分简单介绍模块的使用第二部分回顾堆排序算法第三部分分析中的实现。总结堆排序结合图来理解还是比较好理解的。原文链接：https://www.hongweipeng.com/i... 起步 heapq 模块实现了适用于Python列表的最小堆排序算法。 showImg(https://segmentfaul...

CoderBear 2019-07-30 18:43 评论0 收藏0
排序算法

摘要：排序代码实现和一概念排序算法的稳定性稳定性稳定排序算法会让原本有相等键值的纪录维持相对次序。交换的结果导致结点的值变化了，重复，，的操作，直到没有孩子时跳出代码实现构建初始堆堆排序算法思想大顶堆举例将待排序的序列构造成一个大顶堆。排序代码实现：Java 和 Python 一、概念 1.1 排序算法的稳定性稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序...

kevin 2019-08-19 10:56 评论0 收藏0
排序算法

摘要：排序代码实现和一概念排序算法的稳定性稳定性稳定排序算法会让原本有相等键值的纪录维持相对次序。交换的结果导致结点的值变化了，重复，，的操作，直到没有孩子时跳出代码实现构建初始堆堆排序算法思想大顶堆举例将待排序的序列构造成一个大顶堆。排序代码实现：Java 和 Python 一、概念 1.1 排序算法的稳定性稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序...

binaryTree 2019-07-31 11:11 评论0 收藏0
python之排序操作及heapq模块

摘要：内置的模块接下来我们一一介绍。小伙伴们有没有想我为何介绍这个模块，并且和排序放在一起呢，其实在很多时候我们需要找序列中的前几个最大值或者最小值，使用此模块中的方法是最好不过的了。说到排序，很多人可能第一想到的就是sorted,但是你可能不知道python中其实还有还就中方法哟，并且好多种场景下效率都会比sorted高。那么接下来我就依次来介绍我所知道的排序操作。sorted(iter...

dongfangyiyu 2019-07-30 18:39 评论0 收藏0