用python实现堆排序（附内置函数）

目录

基本概念

自写函数实现

内置函数实现

---

 

基本概念

大根堆:每个节点的值都大于或者等于他的左右孩子节点的值

小根堆:每个结点的值都小于或等于其左孩子和右孩子结点的值

父-->子:i--->左孩子:2*i+1, 右孩子:2*i+2;
子-->父:i--->(i-1)/2; (i为下标元素)

堆排序是一种选择排序，其最坏，最好，平均时间复杂度均为O(nlogn)，同时也是不稳定排序。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，即可得到一个有序序列。

 

大根堆:每个节点的值都大于或者等于他的左右孩子节点的值

小根堆:每个结点的值都小于或等于其左孩子和右孩子结点的值

父-->子:i--->左孩子:2*i+1, 右孩子:2*i+2;
子-->父:i--->(i-1)/2; (i为下标元素)

堆排序是一种选择排序，其最坏，最好，平均时间复杂度均为O(nlogn)，同时也是不稳定排序。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，即可得到一个有序序列。

 

自写函数实现

def sift(li:list,low,high):
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    """
    i=low# 开始的根节点
    j=2*i+1# j开始是左孩子
    tmp=li[low]# tmp把根节点存储进来
    while j<=high: # 只要j位置有数
        if j+1<=high and li[j+1]>li[j]:
            j+=1
        if li[j]>tmp:
            li[i]=li[j]
            i=j
            j=2*i+1
        else:
            li[i]=tmp
            break
    else:
        li[i]=tmp
def heap_sort(li):
    n=len(li)
    for i in range((n-2)//2,-1,-1):
            # i代表建堆的时候调整的部分的根的下标
        sift(li,i,n-1)
    for i in range(n-1,-1,-1):
        li[0],li[1]=li[1],li[0]
        sift(li,0, i - 1)
    print(li)
import random
li=[i for i in range(100)]
random.shuffle(li)
heap_sort(li)

代码效果

 

内置函数实现

# 内置函数
import heapq
import random
li=list(range(100))
random.shuffle(li)
heapq.heapify(li)# 建小根堆
my_=-1
heapq.heappush(li,my_)
for i in range(len(li)):
    print(heapq.heappop(li),end=',')# 往外弹出最小的元素

代码效果