精华内容
下载资源
问答
  • python 堆排序

    2019-08-08 17:14:34
    python 堆排序 堆排序算法是对选择排序的改进,通过利用堆结构,可以减少相比于选择排序的比较次数,进而提高排序效率。堆是一种特殊的二叉树,分为小根堆和大根堆两种。 小根堆(满足3个基本条件): 它是一棵完全...

    python 堆排序

    堆排序算法是对选择排序的改进,通过利用堆结构,可以减少相比于选择排序的比较次数,进而提高排序效率。堆是一种特殊的二叉树,分为小根堆和大根堆两种。
    小根堆(满足3个基本条件):

    • 它是一棵完全二叉树
    • 根节点小于等于它的左右孩子节点
    • 对于根节点的左右子树也满足以上两点

    大根堆(满足3个基本条件):

    • 它是一棵完全二叉树
    • 根节点大于等于它的左右孩子节点
    • 对于根节点的左右子树也满足以上两点

    堆排序算法思想

    1、构建堆
    2、对调首尾元素
    3、调整堆

    先说堆(假设大根堆)的调整,堆的调整:
    对于任一需要调整的节点,设为pos,其左右孩子节点分别为:2pos+1,2pos+2(lists下标从0开始),将pos与其左右孩子比较,若左右孩子都大于pos,则将较大孩子的值与pos交换,(为什么要与较大的孩子交换,因为大根堆需要满足父节点不小于孩子节点),若左孩子或右孩子中的一个大于pos,则将大于pos的孩子与pos交换,若左右孩子都不大于pos,则不用交换。假设我们将pos与其右孩子做了交换,那么下一步就是从右孩子开始递归调整(将右孩子看作pos继续上面的步骤,左孩子不用调整,左孩子已经满足大根堆的条件),因为交换过后的堆不一定还满足大根堆的条件。

    再说构建堆:
    知道了如何调整堆之后,就可以通过调整由lists(原待排序序列)构成的完全二叉树来构建大根堆。具体步骤是:设 i=length//2,从 i - 1到 0 对二叉树进行调整,假设 lists 长度为5,则 i = 5//2 = 2,i - 1 =1,所以从二叉树中下标为1的元素开始调整,直至下标为0的元素也调整完,这就完成了堆的创建。

    最后是对调首尾元素:
    对调首尾元素的目的是将最大元素放在列表最后,而后再对列表的前 length - 1 个元素进行调整为大根堆(首尾元素交换后,原大根堆不再满足大根堆的条件),递归执行以上两个步骤直至排序完成。

    python实现

    #堆排序(升序排列,构建大根堆):
    def heap_adjust(lists,pos,length):
        max_=pos
        lchild=2*pos+1#由于lists下表从0开始,所以左右孩子下标为2*pos+1,2*pos+2
        rchild=2*pos+2
        if max_<length//2:#注意符号是<,堆调整时,必定是从(length//2)-1开始
            if lchild<length and lists[lchild]>lists[max_]:
                max_=lchild
            if rchild<length and lists[rchild]>lists[max_]:
                max_=rchild
            if max_!=pos:#如果max_未发生改变,说明不需要调整
                lists[max_],lists[pos]=lists[pos],lists[max_]
                heap_adjust(lists,max_,length)#递归调整
    def heap_create(lists,length):
        for i in range(length//2)[::-1]:
            heap_adjust(lists,i,length)
    def heap_sort(lists):
        length=len(lists)
        heap_create(lists,length)
        for i in range(length)[::-1]:
            lists[0],lists[i]=lists[i],lists[0]#首尾元素互换,将最大的元素放在列表末尾
            heap_adjust(lists,0,i)#从头再调整,列表长度-1(尾元素已经完成排序,所以列表长度-1)
    lists=[6,1,52,8,777,14,13,0,9,2,2,1]
    heap_sort(lists)
    print(lists)
    
    展开全文
  • Python堆排序

    2019-09-11 10:56:45
    Python堆排序 思想: 构建堆 输出堆 分析: 1. 构建堆 从底向上,从右往左调整堆 示例:图中节点表示索引 调整顺序为:3 --> 2 --> 1 --> 0 调整索引范围:[0, n//2-1],n为数组长度 每次...

    Python堆排序

    思想

    • 构建堆

    • 输出堆

    分析

    1. 构建堆
    • 从底向上,从右往左调整堆

      • 示例:图中节点表示索引

        在这里插入图片描述

        调整顺序为:3 --> 2 --> 1 --> 0

      • 调整索引范围:[0, n//2-1]n为数组长度

    • 每次调整,从上往下(构建大根堆)

      • 比较父节点与子节点的最大值,将父节点与子节点的最大值交换

        父节点索引:father

        子节点索引:father*2+1father*2+2

        注意:边界处理

        • n为偶数,父节点最大索引father=n//2-1时,子节点最大索引可达father*2+2
        • n为奇数,父节点最大索引father=n//2-1时,子节点最大索引可达father*2+1
      • 示例:调整节点 1 时(构建大根堆)

        在这里插入图片描述

        注意:该示例只是为了说明思想,由于构建堆是从底向上,从右往左构建,因此,若实际中遍历至该示例的节点 1 时,该节点以下的各节点已构成堆。

    2. 输出堆
    • 将堆顶元素与堆尾元素交换,更新堆尾前一节点为新的堆尾,调整堆顶至堆尾的各元素,调整方式同上

    • 不断执行上一步,直至输出所有元素

    • 示例

      在这里插入图片描述

    • 最终数组排序即为升序排列(大根堆的情况下)

    附代码(Python3)

    def heap_sort(nums):
        n = len(nums)
        # 构建大根堆
        for i in range(n//2-1, -1, -1):         # 从底向上,从右往左
            heap_adjust(nums, i, n-1)            # 调整(堆,父节点,堆尾节点)
            
        # 输出大根堆(即升序)
        for i in range(n-1, -1, -1):
            nums[0], nums[i] = nums[i], nums[0]  # 交换堆顶与堆尾元素,交换后的堆尾元素即输出值
            heap_adjust(nums, 0, i-1)            # 调整(堆,堆顶,新堆尾节点)
            
    def heap_adjust(nums, father, end):
        # 从上往下调整
        child = father*2+1       # 初始孩子节点                        
        while child <= end:
            # 选择孩子节点中较大者
            if child<end and nums[child+1]>nums[child]:
                child += 1
            # 若孩子节点大于父亲节点,则交换,更新孩子节点为新的父节点,寻找其新的孩子节点
            # 否则跳出
            if nums[child] > nums[father]:
                nums[father], nums[child] = nums[child], nums[father]
                father = child
                child = father*2+1
            else:
                break
    
    li = [50, 16, 30, 10, 60, 90, 2, 80, 70]
    heap_sort(li)
    li
    
    [2, 10, 16, 30, 50, 60, 70, 80, 90]
    
    展开全文
  • Python 堆排序

    2020-07-28 20:46:52
    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来...

     堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

    
    arr=[1,3,11,15,12,14,5]
    def adjust(arr,n,i):
        largest=i
        l=i*2+1
        r=i*2+2
        #判定左子树与根节点的大小
        if l<n and arr[l]>arr[i]:
            largest=l
        # 判定右子树与根节点和左子树较大结点的大小
        if r<n and arr[r]>arr[largest]:
            largest=r
        if largest!=i:
            # 交换结点
            arr[largest],arr[i]=arr[i],arr[largest]
            # 递归调整交换后的分支
            adjust(arr,n,largest)
    
    def heapsort(arr,n):
        for i in range(n//2,-1,-1):
        # for i in range(n // 2, -1, -1):
            adjust(arr,n,i)
        print(arr)
        for i in range(n-1,0,-1):
            arr[0],arr[i]=arr[i],arr[0]
            adjust(arr,i,0)
    
    heapsort(arr,len(arr))
    print(arr)
    

     

    展开全文
  • 主要介绍了Python堆排序原理与实现方法,结合实例形式详细分析了Python堆排序的概念、原理、实现方法及相关操作注意事项,需要的朋友可以参考下
  • python堆排序

    2017-02-25 13:13:29
    import heapq def heapsort(items): heap = [] for item in items: heapq.heappush(heap, item) return [heapq.heappop(heap) for _ in range(len(heap))] nums = [1, 3, 5, 7, 9, 2, 4, 6,
    import heapq
    
    
    def heapsort(items):
        heap = []
        for item in items:
            heapq.heappush(heap, item)
        return [heapq.heappop(heap) for _ in range(len(heap))]
    
    
    nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
    print(heapsort(nums))
    

    展开全文
  • Python堆排序详解

    千次阅读 2019-05-16 17:30:33
    1、堆排序由两个函数组成: 构建堆、堆顶抽取(实现排序) 2、构建堆: 关键参数index:表示建堆的初始索引位置。 满足以下两个条件时,产生递归调用: 当index不在叶节点的第一级父节点 当index不是...
  • 排序算法之python堆排序

    千次阅读 2018-08-25 20:02:45
    堆排序 介绍: 堆排序也是一种选择排序。个人觉得是简单选择排序的优化,借助于二叉树这种数据结构,每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。跟简单...
  • python 堆排序模板

    2020-12-24 21:29:08
    # 调整某一个节点到具体的位置,确保顶为最大值,时间复杂度为logn def heapify(arr, idx, end): # size = len(arr) left = idx * 2 + 1 right = left + 1 while left <= end: # 当前节点非叶子结点 max_...
  • 该模块提供了堆排序算法的实现。 堆是一颗特殊的完全二叉树。 小根堆:满足任一节点都比其孩子节点小 大根堆:满足任一节点都比其孩子节点大
  • 堆排序Heap Sort 是利用堆性质的一种选择排序,在堆顶选出极值 时间复杂度为O(nlogn) 空间复杂度为O(1) 不稳定的排序算法 以类二叉树的形式打印数据 origin=[30,20,80,40,50,10,60,70,90] # 数据存在列表中...
  • 知耻后勇,这几天在网上找了很多写堆排序的帖子,但是帖子质量不好,堆排序是什么不介绍,代码也非常不详细,看了半天没整明白,不过好在今天找出了数据结构课的课本,系统复习后,尝试用Python写出了一个堆排序。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,046
精华内容 14,018
关键字:

python的堆排序

python 订阅