堆排序（heap-sort）

堆排序前传–树与二叉树

• 树是一种数据结构 比如：目录结构
• 树是一种可以递归定义的数据结构
• 树是由n个结点组成的集合：
  • 如果n=0，那这是一棵空树
  • 如果n>0，那么存在1个结点作为数的根结点，其他结点可以分为m个集合，每个集合本身有事一棵树。
    

一些概念：

• 根结点(A),叶子结点(树的末端B,C,H,I,P,Q,K,L,M,N)
• 树的深度（高度），就是最深有几层：4层
• 树的度，就是分出的最多的那个的，A：6度
• 孩子结点/父结点
• 子树：E,I,J,P,Q

二叉树的基础知识

• 度不超过2的树
• 每个结点最多有两个孩子结点
• 两个孩子结点被区分为左孩子结点和右孩子结点

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

完全二叉树：叶结点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

二叉树的存储方式

二叉树的存储方式（表示方式）

• 链式存储方式

• 顺序存储方式

  • 父节点和左孩子结点的编号下标有什么关系？

    • 0-1 1-3 2-5 3-7 4-9
    • 父节点为i： i—>2i+1

  • 父节点和右孩子结点的编号下标有什么关系？

    • 0-2 1-4 2-6 3-8 4-10
    • 父节点为i：i—>2i+2
      

什么是堆

堆：一种特殊的完全二叉树结构

• 大根堆：一棵完全二叉树，满足任一结点都比其孩子结点大
• 小根堆：一棵完全二叉树，满足任一结点都比其孩子节点小
  

堆的向下调整性质

• 假设根节点的左右子树都堆，但根结点不满足堆的性质
• 可以通过一次向下的调整来将其变成一个堆
  

堆排序的过程

1.建立堆（检查每个父节点和它的孩子结点）

2.得到堆顶元素，为最大元素

3.去掉堆顶，将堆最后一个元素放在堆顶，此时可通过一次调整重新使堆有序

4.堆顶元素为第二大元素

5.重复步骤3，直到堆变空

向下调整的函数实现

def sift(li, low, high):
    """ :param li:列表 :param low:堆的根结点位置 :param high:堆的最后一个元素的位置 :return: """
    i = low    #i最开始指向根结点
    j = 2 * i + 1  #j开始是左孩子
    tmp = li[low]  #把堆顶存起来
    while j <= high:   #只要j位置有数
        if j + 1 <= high and li[j+1] > li[j]:   #如果右孩子并且比较大
            j = j + 1   #j指向右孩子
        if li[j] >tmp:
            li[i] = li[j]
            i = j     #往下看一层
            j = 2 * i + 1
        else:     #tmp更大，把tmp放在i的位置上
            li[i] = tmp          #把tmp放在某一领导位置上
            break
            
    else:
        li[i] = tmp   #把tmp放到叶子结点上

堆排序的实现

时间复杂度为：O(ologn)

def sift(li, low, high):
    """ :param li:列表 :param low:堆的根结点位置 :param high:堆的最后一个元素的位置 :return: """
    i = low    #i最开始指向根结点
    j = 2 * i + 1  #j开始是左孩子
    tmp = li[low]  #把堆顶存起来
    while j <= high:   #只要j位置有数
        if j + 1 <= high and li[j+1] > li[j]:   #如果右孩子并且比较大
            j = j + 1   #j指向右孩子
        if li[j] >tmp:
            li[i] = li[j]
            i = j     #往下看一层
            j = 2 * i + 1
        else:     #tmp更大，把tmp放在i的位置上
            li[i] = tmp          #把tmp放在某一领导位置上
            break

    else:
        li[i] = tmp   #把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)   #i-1是最新的high


li = [i for i in range(100)]
import random
print(li)

heap_sort(li)
print(li) 

堆排序中的topk问题

• 现在有n个数，设计算法得到前k大的数。(k<n)
• 解决思路：时间复杂度（O(nlogk))
  • 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数
  • 依次向后遍历原列表，对于表中的元素，如果小于堆顶，则忽视该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整
  • 遍历列表所有元素后，倒序弹出堆顶

def sift(li, low, high):   
    i = low    
    j = 2 * i + 1  
    tmp = li[low]  
    while j <= high: 
        if j + 1 <= high and li[j+1] < li[j]:  
            j = j + 1 
        if li[j] < tmp:
            li[i] = li[j]
            i = j     
            j = 2 * i + 1
        else:     
            break
        li[i] = tmp

def topk(li, k):
    heap = li[0:k]
    for i in range((k-2)//2, -1, -1):
        sift(heap, i, k-1)  #建堆
    for i in range(k, len(li)-1):
        if li[i] > heap[0]:
            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

import random
li = list(range(1000))
random.shuffle(li)

print(topk(li, 10))