转自【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.blogjava.net/Good-Game