【演算法】Ruby 裡的 Heap

joe5491

最近想寫個尋路演算法的時候，查了一下，找不到RGSS裡面有Priority queue(heap)....

沒有Heap怎麼弄A*阿...

所以就很無聊的把C++裡面STL的Priority queue包成個DLL檔，這樣就有Heap可以用了
p.s.這是最大堆

用法:

RUBY 代码复制

$Heap_is_empty = Win32API.new('heap.dll', 'is_empty', 'v', 'i') #檢查是否為空
$Heap_clear = Win32API.new('heap.dll', 'clear', 'v', 'v') #清空
$Heap_push = Win32API.new('heap.dll', 'push', 'ii', 'v') #放入，第一個為優先度，第二個為儲存之數值
$Heap_top = Win32API.new('heap.dll', 'top', 'v', 'i') #取頂部，回傳第二個數值
$Heap_pop = Win32API.new('heap.dll', 'pop', 'v', 'v') #推出
 
$Heap_clear.call()
$Heap_push.call(1,2)
$Heap_push.call(3,4)
$Heap_push.call(-1,9)
if $Heap_is_empty.call() == 0
  p $Heap_top.call()  #4
  $Heap_pop.call()
  p $Heap_top.call()  #2
  $Heap_pop.call()
  p $Heap_top.call()  #9
  $Heap_pop.call()
end

$Heap_is_empty = Win32API.new('heap.dll', 'is_empty', 'v', 'i') #檢查是否為空


$Heap_clear = Win32API.new('heap.dll', 'clear', 'v', 'v') #清空


$Heap_push = Win32API.new('heap.dll', 'push', 'ii', 'v') #放入，第一個為優先度，第二個為儲存之數值


$Heap_top = Win32API.new('heap.dll', 'top', 'v', 'i') #取頂部，回傳第二個數值


$Heap_pop = Win32API.new('heap.dll', 'pop', 'v', 'v') #推出


 


$Heap_clear.call()


$Heap_push.call(1,2)


$Heap_push.call(3,4)


$Heap_push.call(-1,9)


if $Heap_is_empty.call() == 0


  p $Heap_top.call()  #4


  $Heap_pop.call()


  p $Heap_top.call()  #2


  $Heap_pop.call()


  p $Heap_top.call()  #9


  $Heap_pop.call()


end

話說我存xy座標是把一個int拿來當兩個short用(座標不會超過30K嘛

fux2

数组就可以替代heap吧，你用push(<<)和pop以及shift和unshift就行。
你要在RM里写A*用table配合数组我想不到有什么比ruby更好写的了。
要是有强迫症一定要用heap你可以用hash更无脑。
如果还是写不出来那么很遗憾朋友我只能说你要么对ruby理解不深要么对A*理解不够。

PS：补充一下，楼主是不是不知道ruby的数组可以装任意类型……而且不用是单一类型。数组里面套数组也是被允许的。

Sion

怎么写DLL呢，可以给个比较简单源码看看吗？不知楼主用的什么编译器，我用的是VS2010

SuperMario

不错，虽然数组也差不多....