一坐桩、樹相關(guān)知識(shí)

• 樹的深度(高度)：表示樹最深有幾層
• 樹的度：每個(gè)節(jié)點(diǎn)的分叉數(shù)量叫度，所有節(jié)點(diǎn)中分叉數(shù)量最多的是樹的度
• 二叉樹：度不超過2的樹（每個(gè)節(jié)點(diǎn)最多有兩個(gè)分叉)

• 完全二叉樹：葉子節(jié)點(diǎn)只能出現(xiàn)在最下層和次下層封锉，如果從樹根開始按序編號(hào)中間沒有遺漏就是完全二叉樹

  
  
• 滿二叉樹：每一層的節(jié)點(diǎn)都占滿绵跷。也是完全二叉樹
  

完全二叉樹的存儲(chǔ)

使用列表方式存儲(chǔ)，必須存儲(chǔ)完全二叉樹

li = [8,4,12,2,6,10,14,1,3,5]#對(duì)應(yīng)下標(biāo)[0,1,2,3,4,5,6,7,8,9]

• 基于下標(biāo)成福，父節(jié)點(diǎn)找左孩子節(jié)點(diǎn)：
  i -> 2i+1
  基于下標(biāo)碾局，父節(jié)點(diǎn)找右孩子節(jié)點(diǎn)：
  i -> 2i+2

• 基于下標(biāo)，左孩子找父節(jié)點(diǎn)：
  i-> (i-1)/2
  基于下標(biāo)奴艾，右孩子找父節(jié)點(diǎn)：
  i-> (i-2)/2
  孩子找父節(jié)點(diǎn)可以合并為：i->(i-1)//2

二净当、堆的基本概念

堆是一種完全二叉樹

• 大根堆：任意節(jié)點(diǎn)都比孩子節(jié)點(diǎn)大

  
  

• 小根堆：任意節(jié)點(diǎn)都比孩子節(jié)點(diǎn)小

  
  

堆的向下調(diào)整性

根節(jié)點(diǎn)的左右子樹都是堆，根節(jié)點(diǎn)所在的樹自身不是堆蕴潦∠裉洌可以通過一次向下調(diào)整變成一個(gè)堆。

原圖

調(diào)整后的圖

三潭苞、堆排序

構(gòu)造大根堆

從最后一個(gè)有孩子的節(jié)點(diǎn)忽冻，以該節(jié)點(diǎn)為根的樹如果滿足大根堆不做調(diào)整。如果不是大根堆此疹，則利用向下調(diào)整性構(gòu)造一個(gè)大根堆甚颂。
5,4,2,7,0都沒有子節(jié)點(diǎn)蜜猾，單個(gè)節(jié)點(diǎn)本身就是一個(gè)堆，所以從3開始

原圖

構(gòu)造大根堆

挨個(gè)出數(shù)

由于是大根堆振诬，取出的根元素是最大的值蹭睡。圖示第一次取跟元素，取出后剩余元素重新排序赶么，發(fā)現(xiàn)最終得到的不是一個(gè)完全二叉樹肩豁，該方法不符合要求。因?yàn)?strong>堆必須是一個(gè)完全二叉樹辫呻。

代碼實(shí)現(xiàn)

def sift(li,low,high):#堆的向下調(diào)整性
    tmp = li[low]
    i = low
    j = 2 * i + 1
    while j <= high:#第二種情況：i指向葉子節(jié)點(diǎn)，j指向值已經(jīng)超出high范圍
        if j + 1 <= high and li[j+1] > li[j]:#j指向左右兩個(gè)節(jié)點(diǎn)值最大的位置
            j += 1
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:#第一種情況：左右兩個(gè)子節(jié)點(diǎn)都比tmp大
            break
    li[i] = tmp

def heap_sort(li):
    n = len(li)
    #構(gòu)造堆
    for low in range(n//2 - 1,-1,-1):#最后一個(gè)節(jié)點(diǎn)是n-1,找到父節(jié)點(diǎn)n//2 - 1,然后一直到0的位置構(gòu)造堆
        sift(li,low,n-1)#使用整個(gè)數(shù)的最大下標(biāo)n-1作為每個(gè)子樹的high,簡(jiǎn)單且不影響第二種情況判斷
    #挨個(gè)出數(shù)
    for high in range(n-1,-1,-1):#n-1下標(biāo)到0
        li[0],li[high] = li[high],li[0]#當(dāng)前范圍的根元素和high指向的元素?fù)Q位置
        sift(li,0,high-1)#交換后修改high的位置后再重新調(diào)整

向下調(diào)整性兩種退出循環(huán)情況演示：

原圖

第一種終止情況.gif

第二種終止情況.gif

時(shí)間復(fù)雜度

def heap_sort(li):
    ...
    for low in range(n//2 - 1,-1,-1): #O(n)
        sift(li,low,n-1)  #由于while循環(huán)中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))

時(shí)間復(fù)雜度是：O(n*logn)

內(nèi)置模塊實(shí)現(xiàn)

• 內(nèi)置模塊只能構(gòu)造小根堆

import heapq

li = [0,6,2,7,5,8,3,1]
heapq.heapify(li)#內(nèi)置方法構(gòu)造的是小根堆
print(li)#[0, 1, 2, 6, 5, 8, 3, 7]
heapq.heappush(li,9)#插入一個(gè)元素搬葬，重新構(gòu)造堆
print(li)#[0, 1, 2, 6, 5, 8, 3, 7, 9]
item = heapq.heappop(li)#小根堆根元素出來最小的值,剩下的重新構(gòu)造堆
print(item)#0
print(li)#[1, 5, 2, 6, 9, 8, 3, 7]

• heappop()挨個(gè)出數(shù)實(shí)現(xiàn)排序

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]