精华内容
下载资源
问答
  • Python实现堆排序

    2020-07-17 00:14:07
    Python实现堆排序

    Python实现堆排序

    一、堆排序简介

    堆排序(Heap Sort)是利用堆这种数据结构所设计的一种排序算法。

    堆的结构是一棵完全二叉树的结构,并且满足堆积的性质:每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。

    关于二叉树和完全二叉树的介绍可以参考:https://blog.csdn.net/weixin_43790276/article/details/104737870

    堆排序先按从上到下、从左到右的顺序将待排序列表中的元素构造成一棵完全二叉树,然后对完全二叉树进行调整,使其满足堆积的性质:每个节点(叶节点除外)的值都大于等于(或都小于等于)它的子节点。构建出堆后,将堆顶与堆尾进行交换,然后将堆尾从堆中取出来,取出来的数据就是最大(或最小)的数据。重复构建堆并将堆顶和堆尾进行交换,取出堆尾的数据,直到堆中的数据全部被取出,列表排序完成。

    堆结构分为大顶堆和小顶堆:

    1. 大顶堆:每个节点(叶节点除外)的值都大于等于其子节点的值,根节点的值是所有节点中最大的,所以叫大顶堆,在堆排序算法中用于升序排列。

    2. 小顶堆:每个节点(叶节点除外)的值都小于等于其子节点的值,根节点的值是所有节点中最小的,所以叫小顶堆,在堆排序算法中用于降序排列。

    二、堆排序原理

    堆排序的原理如下:

    1. 将待排序列表中的数据按从上到下、从左到右的顺序构造成一棵完全二叉树。

    2. 将完全二叉树中每个节点(叶节点除外)的值与其子节点(子节点有一个或两个)中较大的值进行比较,如果节点的值小于子节点的值,则交换他们的位置(大顶堆,小顶堆反之)。

    3. 将节点与子节点进行交换后,要继续比较子节点与孙节点的值,直到不需要交换或子节点是叶节点时停止。比较完所有的非叶节点后,即可构建出堆结构。

    4. 将数据构造成堆结构后,将堆顶与堆尾交换,然后将堆尾从堆中取出来,添加到已排序序列中,完成一轮堆排序,堆中的数据个数减1。

    5. 重复步骤2,3,4,直到堆中的数据全部被取出,列表排序完成。

    以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

    要进行升序排序,则构造堆结构时,使用大顶堆。

    1. 将待排序列表中的数据按从上到下、从左到右的顺序构造成一棵完全二叉树。

    2. 从完全二叉树的最后一个非叶节点开始,将它的值与其子节点中较大的值进行比较,如果值小于子节点则交换。24是最后一个非叶子节点,它只有一个子节点21,24大于21,不需要交换。

    3. 继续将倒数第二个非叶节点的值与其子节点中较大的值进行比较,如果值小于子节点则交换。节点30有两个子节点5和36,较大的是36,30小于36,交换位置。

    4. 重复对下一个节点进行比较。7小于45,交换位置。

    5. 继续重复,50大于27,不需要交换位置。如果不需要进行交换,则不用再比较子节点与孙节点。

    6. 继续重复,17小于45,交换位置。

    7. 17和45交换位置之后,17交换到了子节点的位置,还需要继续将其与孙节点进行比较。17大于15,不需要交换。

    8. 继续对下一个节点进行比较,10小于50,交换位置。

    9. 10和50交换位置之后,10交换到了子节点的位置,还需要继续将其与孙节点进行比较。10小于于27,交换位置。

    10. 此时,一个大顶堆构造完成,满足了堆积的性质:每个节点(叶节点除外)的值都大于等于它的子节点。

    11. 大顶堆构建完成后,将堆顶与堆尾交换位置,然后将堆尾从堆中取出。将50和21交换位置,交换后21到了堆顶,50(最大的数据)到了堆尾,然后将50从堆中取出。

    12. 将50从堆中取出后,找到了待排序列表中的最大值,50添加到已排序序列中,第一轮堆排序完成,堆中的元素个数减1。

    13. 取出最大数据后,重复将完全二叉树构建成大顶堆,交换堆顶和堆尾,取出堆尾。这样每次都是取出当前堆中最大的数据,添加到已排序序列中,直到堆中的数据全部被取出。

    14. 循环进行 n 轮堆排序之后,列表排序完成。排序结果如下图。

    三、Python实现堆排序

    # coding=utf-8
    def heap_sort(array):
        first = len(array) // 2 - 1
        for start in range(first, -1, -1):
            # 从下到上,从右到左对每个非叶节点进行调整,循环构建成大顶堆
            big_heap(array, start, len(array) - 1)
        for end in range(len(array) - 1, 0, -1):
            # 交换堆顶和堆尾的数据
            array[0], array[end] = array[end], array[0]
            # 重新调整完全二叉树,构造成大顶堆
            big_heap(array, 0, end - 1)
        return array
    
    
    def big_heap(array, start, end):
        root = start
        # 左孩子的索引
        child = root * 2 + 1
        while child <= end:
            # 节点有右子节点,并且右子节点的值大于左子节点,则将child变为右子节点的索引
            if child + 1 <= end and array[child] < array[child + 1]:
                child += 1
            if array[root] < array[child]:
                # 交换节点与子节点中较大者的值
                array[root], array[child] = array[child], array[root]
                # 交换值后,如果存在孙节点,则将root设置为子节点,继续与孙节点进行比较
                root = child
                child = root * 2 + 1
            else:
                break
    
    
    if __name__ == '__main__':
        array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
        print(heap_sort(array))

    运行结果:

    [5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

    代码中,先实现一个big_heap(array, start, end)函数,用于比较节点与其子节点中的较大者,如果值小于子节点的值则进行交换。代码中不需要真正将数据都添加到完全二叉树中,而是根据待排序列表中的数据索引来得到节点与子节点的位置关系。完全二叉树中,节点的索引为i,则它的左子节点的索引为2*i+1,右子节点的索引为2*i+2,有n个节点的完全二叉树中,非叶子节点有n//2个,列表的索引从0开始,所以索引为0~n//2-1的数据为非叶子节点。

    实现堆排序函数heap_sort(array)时,先调用big_heap(array, start, end)函数循环对非叶子节点进行调整,构造大顶堆,然后将堆顶和堆尾交换,将堆尾从堆中取出,添加到已排序序列中,完成一轮堆排序。然后循环构建大顶堆,每次将最大的元素取出,直到堆中的数据全部被取出。

    四、堆排序的时间复杂度和稳定性

    1. 时间复杂度

    在堆排序中,构建一次大顶堆可以取出一个元素,完成一轮堆排序,一共需要进行n轮堆排序。每次构建大顶堆时,需要进行的比较和交换次数平均为logn(第一轮构建堆时步骤多,后面重建堆时步骤会少很多)。时间复杂度为 T(n)=nlogn ,再乘每次操作的步骤数(常数,不影响大O记法),所以堆排序的时间复杂度为 O(nlogn) 。

    2. 稳定性

    在堆排序中,会交换节点与子节点,如果有相等的数据,可能会改变相等数据的相对次序。所以堆排序是一种不稳定的排序算法。

     

    展开全文
  • python实现堆排序

    2019-09-15 21:59:09
    直接放代码,对堆概念模糊者请自行...#python实现堆排序 def heapify(arr,n,i): largest=i left=2*i+1 right=2*i+2 if left<n and arr[largest]<arr[left]: largest=left if right<n and arr[large...

    直接放代码,对堆概念模糊者请自行查询!

    #python实现堆排序
    def heapify(arr,n,i):
        largest=i
        left=2*i+1
        right=2*i+2
        if left<n and arr[largest]<arr[left]:
            largest=left
        if right<n and arr[largest]<arr[right]:
            largest=right
        if largest!=i:
            arr[largest],arr[i]=arr[i],arr[largest]  #python是地址引用,交换
            heapify(arr,n,largest) #下沉式调整
    
    def heapsort(arr):
        n=len(arr)
        for i in range(n-1,-1,-1):
            heapify(arr,n,i)  #将序列构造成大根堆
        #把最大值交换到最后位置,再重新调整为堆,升序排列
        for i in range(n-1,0,-1):
            arr[i],arr[0]=arr[0],arr[i]
            heapify(arr,i,0)
    
    arr=[3,4,1,9,6,0,23]
    heapsort(arr)
    for i in range(len(arr)):
        print(arr[i])
    
    展开全文
  • Python 实现堆排序

    2017-01-15 19:57:45
    Python实现堆排序算法,可运行。欢迎指正!
    def heapadjust(seq, node, size): #adjust heap
        lchild = 2 * node + 1
        rchild = 2 * node + 2
        maxcode = node
        if node <= size / 2 - 1: #if lefthchild or rightchild > root node, exchange the value
            if lchild <= size - 1 and seq[lchild] > seq[maxcode]:
                maxcode = lchild
            if rchild <= size - 1 and seq[rchild] > seq[maxcode]:
                maxcode = rchild
            if maxcode != node:
                tem = seq[node]
                seq[node] = seq[maxcode]
                seq[maxcode] = tem
                heapadjust(seq, maxcode, size) #adjust the heap which root is maxcode
    
    def buildheap(seq, size): #build heap
        for i in range(size / 2 - 1, -1, -1):
            heapadjust(seq, i, size)
    
    def heapsort(seq, size): # we can get the maximum value in each loop and put it at the end of array
        buildheap(seq, size)
        for j in range(size - 1, -1, -1):
            tem = seq[0]
            seq[0] = seq[j]
            seq[j] = tem
            buildheap(seq, j)
        return seq
    
    
    if __name__ == '__main__':
        l = [0, 16, 20, 3, 11, 17, 8]
        print heapsort(l, len(l))
    
    展开全文
  • python 实现堆排序

    2019-07-09 22:45:46
    堆排序是利用 堆进行排序的 堆是一种完全二叉树 堆有两种类型: 大根堆 小根堆 两种类型的概念如下: 大根堆:每个结点的值都大于或等于左右孩子结点 小根堆:每个结点的值都小于或等于左右孩子结点 完全...

    1、概念

    • 堆排序是利用 堆进行排序的

    • 堆是一种完全二叉树

    • 堆有两种类型: 大根堆 小根堆

    • 两种类型的概念如下:

      大根堆:每个结点的值都大于或等于左右孩子结点
      小根堆:每个结点的值都小于或等于左右孩子结点
      在这里插入图片描述
      在这里插入图片描述

    完全二叉树

    完全二叉树 是 一种除了最后一层之外的其他每一层都被完全填充,并且所有结点都保持向左对齐的树,向左对齐指的是:
    在这里插入图片描述

    下面这样的树不是完全二叉树:
    在这里插入图片描述

    如果给上面的大小根堆的根节点从1开始编号,则满足下面关系(下图就满足这个关系):

    在这里插入图片描述

    如果把这些数字放入数组中,则如下图所示:其中,上面的数字是数组下标值,第一个元素占位用。
    在这里插入图片描述

    堆排序的思想(以大根堆为例)

    • 首先将待排序的数组构造出一个大根堆
    • 取出这个大根堆的堆顶节点(最大值),与堆的最下最右的元素进行交换,然后把剩下的元素再构造出一个大根堆
    • 重复第二步,直到这个大根堆的长度为1,此时完成排序。

    下面通过图片看第二步是如何进行的
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    这就是构建大根堆的思想,了解了之后就可以进行编码,编码主要解决两个问题:

    • 如何把一个序列构造出一个大根堆

    • 输出堆顶元素后,如何使剩下的元素构造出一个大根堆

      根据问题进行编码,由于数组下标是从0开始的,而树的节点从1开始,我们还需要引入一个辅助位置,Python提供的原始数据类型list实际上是一个线性表(Array),由于我们需要在序列最左边追加一个辅助位,线性表这样做的话开销很大,需要把数组整体向右移动,所以list类型没有提供形如appendleft的函数,但是在一个链表里做这种操作就很简单了,Python的collections库里提供了链表结构deque,我们先使用它初始化一个无序序列:

    from collections import deque
    L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
       
    L.appendleft(0)
    
    

    总代码:

    from collections import deque
    
    def swap_param(L, i, j):
        L[i], L[j] = L[j], L[i]
        return L
    
    def heap_adjust(L, start, end):
        temp = L[start]
    
        i = start
        j = 2 * i
    
        while j <= end:
            # L[j] 为左右叶子节点中相对大的数字
            if (j < end) and (L[j] < L[j + 1]):
                j += 1
            # 将根结点与叶子节点中较大的数交换
            if temp < L[j]:
                L[i], L[j] = L[j],L[i]
                i = j
                j = 2 * i
            else:
                break
        # L[i] = temp
    
    def heap_sort(L):
        L_length = len(L) - 1
    
        first_sort_count = L_length // 2
        for i in range(first_sort_count):
            heap_adjust(L, first_sort_count - i, L_length)
    
        for i in range(L_length - 1):
            L = swap_param(L, 1, L_length - i)
            heap_adjust(L, 1, L_length - i - 1)
    
        return [L[i] for i in range(1, len(L))]
    
    def main():
        L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])
        # L = deque([56,30,71,18,29,93,44,75,20,65,68,34])
        L.appendleft(0)
        print(heap_sort(L))
    
    if __name__ == '__main__':
        main()
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,146
精华内容 458
关键字:

python实现堆排序

python 订阅