Heapの実装
RubyでHeapのデータ構造を実装します。
class Heap def push(array,elem) n = array.size array << elem while n != 0 i = (n-1) / 2 if (array[n] - array[i]) > 0 tmp = array[n] array[n] = array[i] array[i] = tmp end n = i end end def pop(array) n = array.size.to_i - 1 max_elem = array[0] array[0] = array.pop i = 0 while (j = (2 * i + 1)) < n if((j != n-1) && ((array[j] - array[j+1]) < 0)) j += 1 end if (array[i] - array[j]) < 0 tmp = array[j] array[j] = array[i] array[i] = tmp else break end i = j end return max_elem end end
実行します。
heap = Heap.new() test = [] heap.push(test,20) heap.push(test,5) heap.push(test,15) heap.push(test,4) heap.push(test,3) heap.push(test,9) heap.push(test,10) heap.push(test,6) puts heap.pop(test) puts heap.pop(test) puts heap.pop(test) puts heap.pop(test) puts heap.pop(test) puts heap.pop(test)
実行結果です。
20 15 10 9 6 5 Complete(0)
下記のWebページを参考にさせていただきました。
優先度付き待ち行列