二叉堆[更新] - Project1 - Powered by Discuz!

#==============================================================================
# ■ 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

复制代码

#--------------------------------------------------------------------------
# ● 转化
#--------------------------------------------------------------------------
def self.new(ar) #数组转化为二叉堆结构
if ar.class != Array
p "数据类型不正确";exit
end
ar=ar.sort #生成最小堆
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
elsif ar[pos_s2-1] == nil #当右孩子为空时
pos_min = pos_s1 #最小节点值直接赋给左孩子
else
#比较出较小的节点
if ar[pos_s1-1] > ar[pos_s2-1]
pos_min = pos_s2
else
pos_min = pos_s1
end
end
if !fs(ar[pos-1],ar[pos_min-1])
ar[pos-1],ar[pos_min-1] = ar[pos_min-1],ar[pos-1]
pos = pos_min;next
end
break
end
return ar
end
end

复制代码