Heapの実装~逆順~
RubyでHeapのデータ構造を実装します。
通常大きい値から取り出しますが、
今回は小さい値から取り出す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 min_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 min_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)
実行結果です。
3 4 5 6 9 10 Complete(0)