Python3實現最小堆建堆算法

今天看Python CookBook中關於“求list中最大(最小)的N個元素”的內容，介紹了直接使用python的heapq模塊的nlargest和nsmallest函數的解決方式，記得學習數據結構的時候有個堆排序算法，所以順便研究了一下“堆”結構（這裡特指二叉堆）。

概念

所謂二叉堆（binary heap）實際上就是一顆特殊的完全二叉樹，其特殊性在於：

1. 二叉樹中所有的父節點的值都不大於/不小於其子節點；
2. 根節點的值必定是所有節點中最小/最大的。

父節點值不大於子節點且根節點值最小稱為最小堆，反之稱為最大堆。最大堆和最小堆沒有本質上的區別。如下圖是一個典型的最小堆：

算法

現在實現一個對給定list完成初始建堆的算法。（以最小堆為例）

假設 list = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]

先記錄一個自己當時看堆結構時琢磨出來的算法，後來查了查資料發現不是最優的。

渣渣算法

直接根據list中元素的index構建二叉樹，這裡我們不使用鏈表，完全以列表實現並以0為基（根節點index為0）：

根據完全二叉樹的特點（節點如果存在右子節點，則必存在左子節點且如果右子節點存在子節點，則左子節點必存在左右子節點），元素個數為N的完全二叉樹的最後一個擁有子節點的節點的index為N//2 -1 。

為了實現二叉樹中所有父節點的值不大於其子節點（特性1），只需要從根節點（index = 0）遍歷到最後一個擁有子節點的節點（index = N//2 -1），將父節點與其子節點值作比較，必要時進行交換即可。完成一次上述過程後就能完成最底層節點的歸位了。元素個數為N的二叉樹層數為ceil(log₂n),因此一共執行floor(log₂n)次上述過程就能實現最小堆的建堆了。算法如下：

#!/usr/bin/env python

import os
import sys
import math

def heap(list):
    n = len(list)
    for i in range(0,int(math.log(n,2))):                #每循環依次就完成了一層的建堆
        for j in range(0,n//2):
            k = 2*j+2 if 2*j+2 < n and list[2*j+2] < list[2*j+1] else 2*j+1    #讓k成為較小的子節點的index
            if list[j] > list[k]:
                (list[j],list[k]) = (list[k],list[j])         #交換值

def main(argv):
    list = [int(arg) for arg in argv]
    heap(list)
    print(list)
if __name__ == "__main__":
    if len(sys.argv) > 1:
        main(sys.argv[1:])

這是自頂向下的遍歷方式，還可以自底向上遍歷，則首先歸位的是根節點。

很明顯，這個算法的復雜度為O(nlogn), 但實際上，最優的建堆算法的復雜度是O(n)，而且這個算法還使用了數學函數。。。

最優算法

下面貼一個使用遞歸的最優算法：

思路還是一樣，直接根據list構建二叉樹，然後從最後一個擁有子節點的節點向上遍歷，使用下沉算法將遍歷到的每一個子樹變成二叉堆。最終整個二叉樹就成為一個二叉堆。

#!/usr/bin/env python

import os
import sys

def sink(list,root):
    if 2*root+1 < len(list):
        k = 2*root+2 if 2*root+2 < len(list) and list[2*root+2] < list[2*root+1] else 2*root+1     #讓k成為較小的子節點的index
        if list[root] > list[k]:
            (list[root],list[k]) = (list[k],list[root])     #交換值
            sink(list,k)              #對子節點為根節點的子樹建堆

def main(argv):
    list = [int(arg) for arg in argv]
    for i in range(len(list)//2-1,-1,-1):
        sink(list,i)
    print(list)
if __name__ == "__main__":
    if len(sys.argv) > 1:
        main(sys.argv[1:])

兩種算法運行截圖：

堆排序

最後說一下堆排序，建堆完成後，排序就簡單了：

將根節點（即list[0]）彈出：list.pop(0)，然後將最後一個節點放到根節點位置，對剩下的list再次進行建堆（針對算法1，算法2則是直接調用sink方法即可）。反復此過程就能輸出排序結果。

想要直接在list內排序的話，則不彈出根節點，而是直接將根節點和最後一個節點交換位置，反復調用sink方法（但是不能再用len(list)，而是給定一個從len(list)依次遞減的參數，避免讓已排序好的節點繼續參與建堆）

《Python核心編程 第二版》.(Wesley J. Chun ).[高清PDF中文版] http://www.linuxidc.com/Linux/2013-06/85425.htm

《Python開發技術詳解》.( 周偉,宗傑).[高清PDF掃描版+隨書視頻+代碼] http://www.linuxidc.com/Linux/2013-11/92693.htm

Python腳本獲取Linux系統信息 http://www.linuxidc.com/Linux/2013-08/88531.htm

在Ubuntu下用Python搭建桌面算法交易研究環境 http://www.linuxidc.com/Linux/2013-11/92534.htm

Python 的詳細介紹：請點這裡
Python 的下載地址：請點這裡