二叉堆[更新]

雷欧纳德

以下引用美兽于2008-3-17 14:58:34的发言：

一般对于想快速需求最值的环境下，都能用的上，例如棋类搜索，评估等。

在处理大数据量时效果比较明显，数据量很小时反而显的累赘，与普通的二叉树相比强调节点顺序。

数据越多越能显示出其强大
但是如果只有几十个数据，那么用二叉堆是吃力不讨好的事情
比较适合有几千个数据的大型游戏使用

二叉堆的一个特点就是，只关心第一个数据是否是最值，不关心其后的数据的排列顺序

不过数据少的时候觉得用二分法插入数组其实更有效一点

dbshy

多么熟悉的二叉堆,久违了,让我想起了高中时的OI生涯

雪流星

我只是想提一下
堆的英文不是head而是heap{/pz}

MS沒人指出

另外在堆當中,MS不能有相等的值吧?
也就沒有父結點等於子結點的可能性了

還是我記錯了@@

雷欧纳德

为啥不能有相等情况呢？
求最值并不需要保证最值得唯一性的说

雪流星

想起了
二元搜索樹(Binary Search Tree)才是要求不能相等的
因為搜索為目的,因此每個結點之值都是獨一無二的
{/hx}

雷欧纳德

二叉树的子孙太多鸟{/qiang}

御灵

发布完毕。
http://rpg.blue/web/htm/news1067.htm
vip+4

威廉华莱士

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

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...所以这不是我们要的结果....
相信这只是猫哥哥一时疏忽造成的....改了一下代码,让它每次只与子节点中较小的比较,这样问题大概就能解决了...

1. 
   
2. #--------------------------------------------------------------------------
   
3.   # ● 删除
   
4.   #--------------------------------------------------------------------------
   
5.   def self.del(ar,pos) #从堆里删除数据
   
6.    
   
7.     if ar[pos - 1] !=nil
   
8.     ar[pos - 1] = ar[ar.size - 1]; ar.pop
   
9.    
   
10.     loop do #比较子结点
    
11.       pos_s1 = pos*2;pos_s2 = pos*2 + 1
    
12.       if ar[pos_s1-1] == nil and ar[pos_s2-1] == nil #已经无子结点
    
13.         break
    
14.       elsif ar[pos_s2-1] == nil  #当右孩子为空时
    
15.         pos_min = pos_s1     #最小节点值直接赋给左孩子
    
16.       else
    
17.        #比较出较小的节点
    
18.        if ar[pos_s1-1] > ar[pos_s2-1]
    
19.           pos_min = pos_s2
    
20.         else
    
21.           pos_min = pos_s1
    
22.         end
    
23.       end
    
24.       if !fs(ar[pos-1],ar[pos_min-1])
    
25.         ar[pos-1],ar[pos_min-1] = ar[pos_min-1],ar[pos-1]
    
26.         pos = pos_min;next
    
27.       end
    
28.      
    
29.         break
    
30.     end
    
31.    
    
32.     return ar
    
33.   end
    
34. end
    

复制代码