A Ruby implementation of a Binomial Min Heap data structure using Array-Based representation

heap.rb

require 'test/unit'

class Heap
    Node = Struct.new :key, :value do 
        include Comparable

        def <=> (other)
            self.key <=> other.key
        end
    end

    def initialize(items = [])
        @elements = []

        items.to_a.each { |item| push item }
    end

    def push(key, value=key)
        @elements << Node.new(key, value)
        bubble_up(@elements.size - 1)
        [key, value]
    end

    alias_method :<<, :push

    def pop
        return nil if self.empty?
        swap 0, @elements.length - 1

        n = @elements.pop
        bubble_down 0
        
        [n.key, n.value]
    end

    def min
        return nil if self.empty?

        n = @elements[0]
        [n.key, n.value]
    end

    alias_method :front, :min

    def clear
        @elements = []
    end

    def empty?
        @elements.empty?
    end

    def size
        @elements.size
    end

    alias_method :length, :size

private
    
    def bubble_up(i)
        parent_id = parent i
        if i > 0 && @elements[i] < @elements[parent_id]
            swap i, parent_id
            bubble_up parent_id
        end 
    end

    def bubble_down(i)
        return unless left? i 
        left_id = left i
        smaller_id = left_id

        if right? i
            right_id = right i
            smaller_id = right_id if @elements[right_id] < @elements[left_id] 
        end

        if @elements[smaller_id] < @elements[i]
            swap i, smaller_id
            bubble_down smaller_id
        end
    end

    def swap(i, j)
        @elements[i], @elements[j] = @elements[j], @elements[i]
    end

    def parent(i)
        (i - 1) / 2
    end

    def left(i)
        2 * i + 1
    end

    def right(i)
        2 * i + 2
    end

    def parent?(i)
        i != 0
    end

    def left?(i)
        left(i) < @elements.size
    end

    def right?(i)
        right(i) < @elements.size
    end
end

if __FILE__ == $0
    class TestHeap < Test::Unit::TestCase
        def setup
            @heap = Heap.new
        end

        def teardown
            @heap.clear
        end

        def test_simple
            @heap.push 2, "world"
            @heap.push 1, "hello"

            assert [email protected]?
            assert_equal 2, @heap.size

            assert_equal [1, "hello"], @heap.min
            assert_equal [1, "hello"], @heap.pop
            assert_equal 1, @heap.size

            assert_equal [2, "world"], @heap.min
            assert_equal [2, "world"], @heap.pop
            assert_equal 0, @heap.size 

            assert @heap.empty?
        end
    end
end