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