堆排序的基础

wuchangjian2021-11-09 23:26:31编程学习

堆排序

  • 复杂度O(nlogn)
  • sift(li,low,high)函数,logn 相当于二分法,因为给tmp找一个位置,只能走二叉树的一个叉
  • n为heap_sort(li)中的两个for 循环

二叉树

  • 度为2

满二叉树

  • 每一层的节点数都达到最大值

完全二叉树

  • 叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
    func4()

  • 最下面一层可以不满,须从左往右排列

二叉树的存储方式

  • 链式存储方式

  • 顺序存储方式
    func4()

    • 父节点与左孩子节点的编号下标 i->2i+1
    • 父节点与右孩子节点的编号下标 i->2i+2
    • 孩子节点与父节点的编号下标 i->(i-1)//2

  • 一种特殊的完全二叉树
    • 大根堆:各个父节点都比孩子节点大
    • 小跟堆:各个父节点都比孩子节点小

堆的向下调整性质

  • 当根节点的左右子树是堆,其本身并不是堆,通过一次向下调整,来把它变成堆

堆排序

建立堆

  • 下级先有序,看最后一个非叶子节点
  • 自右而左,自下而上
func4()

挨个出数 堆建立好的情况下

  • 去掉堆顶,将堆最后一个元素(作为棋子)放到堆顶,一次向下调整,使堆有序
  • 调整过后,堆顶为第二大元素
  • 重复 前两步,直至堆变空

调整函数

大跟堆
def sift(li,low,high):
    '''
    li:列表;
    low:根节点,要调整的堆的根节点;
    high:堆的最后一个元素的位置;
    '''
    i=low #i指向要调整的堆的根节点
    j=2*i+1 #左孩子
    tmp=li[low]
    while j<=high:#j位置有数,不出范围
        if j+1<=high and li[j+1]>li[j]:
            j=j+1 #右孩子存在且比较大
        if li[j]>tmp:
            li[i]=li[j]
            i=j #li[j]>tmp,更新i,j,往下看一层
            j=2*i+1
        else:
            li[i]=tmp #更新后,li[j]不大于tmp
            break
    else:
        li[i]=tmp #j出范围,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):
        '''
        挨个输出
        i指向当前堆的最后一个元素
        '''
        li[0],li[i]=li[i],li[0]
        sift(li,0,i-1)
    return li

li=[0,2,52,26,31]

print(heap_sort(li))

topk问题

  • 现有n个数,设计算法得到前k个数
    • 堆排序
  小跟堆
def sift(li,low,high):
    '''
    li:列表;
    low:根节点,要调整的堆的根节点;
    high:堆的最后一个元素的位置;
    '''
    i=low #i指向要调整的堆的根节点
    j=2*i+1 #左孩子
    tmp=li[low]
    while j<=high:#j位置有数,不出范围
        if j+1<=high and li[j+1]< li[j]:
            j=j+1 #右孩子存在且比较大
        if li[j]< tmp:
            li[i]=li[j]
            i=j #li[j]>tmp,更新i,j,往下看一层
            j=2*i+1
        else:
            li[i]=tmp #更新后,li[j]不大于tmp
            break
    else:
        li[i]=tmp #j出范围,tmp找到位置
 def topk(li,k):
    n=len(li)
    heap=li[0:k]#需修改上述的sift函数,取列表的前k个元素,建立一个小跟堆,堆目前是第k大的元素
    for i in range ((k-2)//2,-1,-1):
        sift(heap,i,k-1)#建堆
    for i in range (k,n-1):
        if li[i]>heap[0]:#遍历k之后的元素,与堆顶元素比较,
            heap[0]=li[i]
            sift(heap,0,k-1)
    for i in range(k-1,-1,-1):
        heap[0],heap[i]=heap[i],heap[0]#挨个出数
        sift(heap,0,i-1)
    return heap

相关文章

线性回归(Linear Regression with One Variable)

线性回归(Linear Regression with One Variable)

2.1 线性回归算法模型表示 让我们通过一个例子来开始:这个例子是预测...

密码杂凑算法的应用

密码杂凑算法的直接应用就是产生消息摘要,进一步可以检验数据的完整性...

css常见问题--精灵技术sprite

目录         产生原因                 原理       ...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。