A Ruby implementation of a Heapsort Algorithm using a Binomial Min Heap data structure

heap.rb

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

heapsort.rb

require 'test/unit'

require_relative 'heap'

module Sort
    extend self

    def heapsort(container)
        heap = Heap.new container

        result = []
        result << heap.pop.first until heap.empty?
        result
    end
end

if __FILE__ == $0
    class TestHeapsort < Test::Unit::TestCase
        def test_heapsort
            unsorted = [3, 5, 2, 4, 6]
            sorted = [2, 3, 4, 5, 6]

            assert_equal sorted, Sort.heapsort(unsorted)
        end
    end
end