一、树相关知识

• 树的深度(高度)：表示树最深有几层
• 树的度：每个节点的分叉数量叫度，所有节点中分叉数量最多的是树的度
• 二叉树：度不超过2的树（每个节点最多有两个分叉)

• 完全二叉树：叶子节点只能出现在最下层和次下层，如果从树根开始按序编号中间没有遗漏就是完全二叉树

  
  
• 满二叉树：每一层的节点都占满。也是完全二叉树
  

完全二叉树的存储

使用列表方式存储，必须存储完全二叉树

li = [8,4,12,2,6,10,14,1,3,5]#对应下标[0,1,2,3,4,5,6,7,8,9]

• 基于下标，父节点找左孩子节点：
  i -> 2i+1
  基于下标，父节点找右孩子节点：
  i -> 2i+2

• 基于下标，左孩子找父节点：
  i-> (i-1)/2
  基于下标，右孩子找父节点：
  i-> (i-2)/2
  孩子找父节点可以合并为：i->(i-1)//2

二、堆的基本概念

堆是一种完全二叉树

• 大根堆：任意节点都比孩子节点大

  
  

• 小根堆：任意节点都比孩子节点小

  
  

堆的向下调整性

根节点的左右子树都是堆，根节点所在的树自身不是堆。可以通过一次向下调整变成一个堆。

原图
调整后的图

三、堆排序

构造大根堆

从最后一个有孩子的节点，以该节点为根的树如果满足大根堆不做调整。如果不是大根堆，则利用向下调整性构造一个大根堆。
5,4,2,7,0都没有子节点，单个节点本身就是一个堆，所以从3开始

原图
构造大根堆

挨个出数

由于是大根堆，取出的根元素是最大的值。图示第一次取跟元素，取出后剩余元素重新排序，发现最终得到的不是一个完全二叉树，该方法不符合要求。因为堆必须是一个完全二叉树。

为了得到一个完全二叉树，当取出根元素后，可以利用树的最后一个元素顶替上去，再利用向下调整性重新排序后取出根元素，不断重复。每次取的根元素排列得到升序的结果，即实现了堆排序。

代码实现

def sift(li,low,high):#堆的向下调整性
    tmp = li[low]
    i = low
    j = 2 * i + 1
    while j <= high:#第二种情况：i指向叶子节点，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:#第一种情况：左右两个子节点都比tmp大
            break
    li[i] = tmp

def heap_sort(li):
    n = len(li)
    #构造堆
    for low in range(n//2 - 1,-1,-1):#最后一个节点是n-1,找到父节点n//2 - 1,然后一直到0的位置构造堆
        sift(li,low,n-1)#使用整个数的最大下标n-1作为每个子树的high,简单且不影响第二种情况判断
    #挨个出数
    for high in range(n-1,-1,-1):#n-1下标到0
        li[0],li[high] = li[high],li[0]#当前范围的根元素和high指向的元素换位置
        sift(li,0,high-1)#交换后修改high的位置后再重新调整

向下调整性两种退出循环情况演示：

原图
第一种终止情况.gif
第二种终止情况.gif

时间复杂度

def heap_sort(li):
    ...
    for low in range(n//2 - 1,-1,-1): #O(n)
        sift(li,low,n-1)  #由于while循环中j = 2 * i + 1，所以是O(logn)

    for high in range(n-1,-1,-1): #O(n)
        li[0],li[high] = li[high],li[0] #O(1)
        sift(li,0,high-1) #O(log(n))

时间复杂度是：O(n*logn)

内置模块实现

• 内置模块只能构造小根堆

import heapq

li = [0,6,2,7,5,8,3,1]
heapq.heapify(li)#内置方法构造的是小根堆
print(li)#[0, 1, 2, 6, 5, 8, 3, 7]
heapq.heappush(li,9)#插入一个元素，重新构造堆
print(li)#[0, 1, 2, 6, 5, 8, 3, 7, 9]
item = heapq.heappop(li)#小根堆根元素出来最小的值,剩下的重新构造堆
print(item)#0
print(li)#[1, 5, 2, 6, 9, 8, 3, 7]

• heappop()挨个出数实现排序

import heapq

li = [0,6,2,7,5,8,3,1]
heapq.heapify(li)
res = [heapq.heappop(li) for i in range(len(li))]
print(res)
>>>[0, 1, 2, 3, 5, 6, 7, 8]