二叉堆[更新]

猫哥哥 · 发表于 2008-3-17 19:02:07

加入我们，或者，欢迎回来。

您需要登录才可以下载或查看，没有帐号？注册会员

x

在论坛里搜索“二叉堆”，没有结果。于是把自己写的发出来。或许还有不正确、不成熟的地方，请指正。
至于，二叉堆可以做什么……将一个数插入到10000个数的数组中，在顺序排列结构的数组里，挨个比较的方法来确定新插入数的位置，最坏的情况得比较10000次；如果用二叉堆的结构，节点比较，最坏的情况则需要比较13次。
有时候，我们需要的仅仅是最大值（最小值），比如在A*寻路里面，取最小F值，就可以应用到二叉堆。

二叉堆（Binary Head）是什么？
二叉堆是一种特殊的堆，二叉堆是完全二元树或者是近似完全二元树。二叉堆满足堆特性：父结点的键值总是大於或等于任何一个子节点的键值。如果想了解更多的内容，在搜索引擎里搜一下吧，也不是一两句话能说清楚，篇幅有限就不赘述了。脚本的具体用法，在脚本里有标注。

#==============================================================================
# ■ Binary_Head
# by 猫哥哥
#------------------------------------------------------------------------------
# 　将数组(Array)转化为二叉堆，并实现堆数据的添加、删除和修改的模块。此模块的使
# 用方法见脚本内容。此为最小堆。如果要用最大堆，把脚本里的"<="和">="替换一下就
# 行了。
#==============================================================================
# 使用方法：
#
# Binary_Head.new(ar) 将数组ar转化为二叉堆
#
# Binary_Head.add(bh,item) 往二叉堆bh里，添加数据item
#
# Binary_Head.del(bh,pos) 删除二叉堆bh里，第pos个数据
#
# Binary_Head.alt(bh,pos,item) 修改二叉堆bh里的第pos个数据的值
#==============================================================================
# 示例：
# eg = [10,30,24,34,38,30,20]
# eg = Binary_Head.new(eg)
# p eg # => [10,30,20,34,38,30,24]
# eg = Binary_Head.add(eg,17)
# p eg # => [10,17,20,30,38,30,24,34]
# Binary_Head.del(eg,1)
# p eg # => [17,30,20,34,38,30,24]
#
#==============================================================================
module Binary_Head
#--------------------------------------------------------------------------
# ● 转化
#--------------------------------------------------------------------------
def self.new(ar) #数组转化为二叉堆
ar_n = []
if ar.class != Array
p "数据类型不正确";exit
end
for i in ar
add(ar_n,i)
end
return ar_n #生成堆
end
#--------------------------------------------------------------------------
# ● 添加
#--------------------------------------------------------------------------
def self.add(ar,item) #往堆里添加数据
ar.push item
pos = ar.size
loop do #比较父节点
if pos == 1 #已经在顶端
break
end
pos_f = pos/2
if ar[pos-1] >= ar[pos_f-1]
break
else
ar[pos_f-1],ar[pos-1]=ar[pos-1],ar[pos_f-1] #交换子结点与父节点
pos = pos_f #传递下标
end
end
return ar
end
#--------------------------------------------------------------------------
# ● 删除
#--------------------------------------------------------------------------
def self.del(ar,pos) #从堆里删除数据
if ar[pos - 1] !=nil
ar[pos - 1] = ar[ar.size - 1]; ar.pop
loop do #比较子结点
pos_s1 = pos*2;pos_s2 = pos*2 + 1
if ar[pos_s1-1] == nil and ar[pos_s2-1] == nil #已经无子结点
break
end
if !fs(ar[pos-1],ar[pos_s1-1])
ar[pos-1],ar[pos_s1-1] = ar[pos_s1-1],ar[pos-1]
pos = pos_s1;next
end
if !fs(ar[pos-1],ar[pos_s2-1])
ar[pos-1],ar[pos_s2-1] = ar[pos_s2-1],ar[pos-1]
pos = pos_s2;next
end
break
end
return ar
end
end
def self.fs(father,son)
if son == nil
true
else
father <= son ? true : false
end
end
#--------------------------------------------------------------------------
# ● 修改
#--------------------------------------------------------------------------
def self.alt(ar,pos,item) #修改数据
del(ar,pos);add(ar,item)
return ar
end
end

复制代码

以下为更新
早上进6r我这里网速还比较快，其他时间根本进不来，后来发现还有无图版能凑合凑合……趁现在能上有图版时编辑一下帖子= =

我一直在思考一个问题。在生成最小堆的时候，或许可以用Array.sort来生成，会比较快，当然要是最大堆的话，再Array.reverse反转一下。由于最后生成的数组是升序排序（降序排序）的，其后面的数总大于等于（小于等于）前面的数。比如，array[p]<=array[p*2] array[p]<=array[p*2+1]，满足二叉堆的性质。

#--------------------------------------------------------------------------
# ● 转化
#--------------------------------------------------------------------------
def self.new(ar) #数组转化为二叉堆结构
if ar.class != Array
p "数据类型不正确";exit
end
ar=ar.sort #生成最小堆
return ar
end

复制代码

看了大家的讨论，自己动手测试了一下。
仅就单次求最值的话，用ruby自带的sort排序会快很多，min和max也是。
二叉堆的快速，只是体现在了之后维护新的数据节省的时间上吧。

突然想起Ruby里可以直接用a,b=b,a来交换变量……脚本里传递变量的temp用不着了。编辑之。

威廉华莱士 · 发表于 2009-4-21 02:24:12

刚才从技术区某帖找到了这一帖,猫哥哥总能写出一些很有趣的代码,呵呵~~~不过看了一下具体算法,感觉删除部分,存在问题....
运行一下这段:

ar = [1,2,3,4,5,6,7,8,9]
Binary_Head.new(ar)
ar = Binary_Head.del(ar,2)
p ar
ar = Binary_Head.del(ar,2)
p ar

出来的结果是:[1,4,3,8,5,6,7,9]
[1,8,3,9,5,6,7]
显然第一个结果是我们想要的,但第二个,却与我们要的最小二叉堆不符了,因为最小二叉堆其父节点总小于其子节点,而明显8会大于其子节点5...所以这不是我们要的结果....
相信这只是猫哥哥一时疏忽造成的....改了一下代码,让它每次只与子节点中较小的比较,这样问题大概就能解决了...