轉自【http://www.cnblogs.com/coderzh/archive/2008/09/22/1296195.html
】
作者：
CoderZh（
CoderZh的技術博客 - 博客園）
出處：
http://coderzh.cnblogs.com/
# 我這 加了些 個人理解的 說明
#encoding:UTF-8
# [遞歸] - 單條路 自下往上排序
def heap_adjust(data, s, m):
if 2 * s > m:return
# 聲明 預設父節點位置
temp = s - 1
# [左]子節點值 大于 父節點值 : 預設父節點位置 為 左子節點位置
if data[2*s - 1] > data[temp]: temp = 2*s-1
# [右]子節點值 大于 預設父節點 : 預設父節點位置 為 右子節點位置
if 2 * s <= m - 1 and data[2*s] > data[temp]: temp = 2 * s
# 交換值 滿足 堆特性 此為 [ 父節點 小于 子節點 ]
if temp <> s - 1:
data[s - 1], data[temp] = data[temp], data[s - 1]
heap_adjust(data, temp + 1, m)
def heap_sort(data):
m = len(data) / 2
# 構建 堆樹
# 測試數據 [3,2,1] 數組值為 所以非底層葉節點
for i in range(m , 0, -1):
heap_adjust(data, i, len(data))
# 從堆樹中 [出棧] 排序輸出
# 測試數據 [5, 4, 3, 2]
data[0], data[-1] = data[-1], data[0]
for n in range(len(data) - 1, 1, -1):
heap_adjust(data, 1, n)
data[0], data[n - 1] = data[n-1], data[0]
data=[2,3,6,3,868,9,8,-1]
heap_sort(data)
print data
# [-1, 2, 3, 3, 6, 8, 9, 868]
轉自 【 http://www.cppblog.com/guogangj/
】
堆存儲
堆 入棧 復雜度為Ο(logn)
堆 出棧 Ο(logn)
整理 www.aygfsteel.com/Good-Game