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)