Skynet

---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks

转自【
http://www.cnblogs.com/coderzh/archive/2008/09/22/1296195.html
作者:CoderZhCoderZh的技术博客 - 博客园
出处:http://coderzh.cnblogs.com/
# 我这 加了些 个人理解的 说明
#encoding:UTF-8
#
 [递归] - 单条路 自下往上排序 
def heap_adjust(data, s, m):
    
if 2 * s > m:return
   
    
# 声明 预设父节点位置
    temp = s - 1
    
    
# [左]子节点值 大于 父节点值  :  预设父节点位置 为 左子节点位置
    if data[2*- 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) - 11-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
posted on 2009-12-01 12:05 刘凯毅 阅读(1473) 评论(0)  编辑  收藏 所属分类: 算法/函数

只有注册用户登录后才能发表评论。


网站导航: