树

树是一种可以递归定义的数据结构

树是由n个节点组成的集合

• n=0 空树

• n>0 一个根节点，其他节点分为m个集合，每个集合本身又是一棵树

一些概念

• 根节点，叶子节点

• 树的深度（高度）

• 树的度

• 孩子节点、父节点

• 子树

二叉树

• 度不超过2的树（节点最多有两个叉）特殊的树

• 满二叉树

• 完全二叉树
  

  调整

  堆排序过程

• 1. 建立堆

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

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

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

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

     import random
     
     # 调整
     def sift(lst, low, high):
         child = 2 * low + 1  # 左孩子
         tmp = lst[low]
         while child < high:  # 孩子在堆里
             # 如果有右孩子且比左孩子大（找到左右孩子中较大的那个）
             if child + 1 <= high and lst[child] < lst[child+1]:
                 child += 1  # 孩子指向右孩子
     
             # 孩子比父节点大
             if lst[child] > tmp:
                 lst[low] = lst[child]  # 孩子调整到父节点上
                 low = child  # 孩子成为新的父节点点
                 child = 2 * low + 1  # 新的孩子节点
             else:
                 break
     
         lst[low] = tmp  # 根节点放到父亲位置
     
     # 堆排序
     def heap_sort(lst):
         n = len(lst)  # 列表总长度，也就是最后一个值
         for i in range(n//2 - 1, -1, -1):
             sift(lst, i, n-1)
     
         # i指向堆的最后
         for i in range(n-1, -1, -1):
             # 根节点取出，最后一个孩子上位
             lst[0], lst[i] = lst[i], lst[0]
             sift(lst, 0, i-1)  # 调整出新根节点
     
     lst = list(range(10))
     random.shuffle(lst)
     heap_sort(lst)
     print(lst)
     # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]