Simple Heap Data Structure in Ruby

class Heap

    # Initialize our Heap
    # To use: my_heap = Heap.new
    def initialize
        @storage = Array.new
    end

    # Test if the Heap is empty.
    # To use: my_heap.empty?
    def empty?
        return @storage.length == 0
    end

    # Insert an item into the Heap
    # Increases the size of the Heap by 1
    # To use: my_heap.insert(item)
    def insert(item)
        @storage << item

        location = @storage.length - 1
        parent = (location - 1) / 2

        while parent >= 0 and @storage[location] > @storage[parent]
            temporary = @storage[parent]
            @storage[parent] = @storage[location]
            @storage[location] = temporary

            location = parent
            parent = (location - 1) / 2
        end

    end

    # Return the top of the Heap (which is the largest value)
    # Does not change the size of the heap.
    # To use: my_heap.top
    def top
        if empty?
            raise 'No elements in the heap.'
        end

        return @storage[0]
    end

    # Pops the top of the Heap and returns it.
    # This reduces the size of the Heap by 1
    # To use: my_heap.pop
    def pop

       if empty?
           raise 'No elements in the heap to pop.'
       end

       top_value = @storage[0]

       # Begin the percolate down algorithm
       @storage[0] = @storage[-1]
       @storage.pop

       root = 0
       child = 2 * root + 1

       while root < @storage.length - 2
           if child + 1 < @storage.length and @storage[child] < @storage[child+1]
               child = child + 1
           end

           if @storage[root] < @storage[child]
               temporary = @storage[root]
               @storage[root] = @storage[child]
               @storage[child] = temporary

               root = child
               child = 2 * child + 1
           else
               break
           end
       end

       return top_value
    end

end

1. sp0rus reblogged this from jcchurch and added:

   The Heap, otherwise known as the “Data Structure of Pure Awesome”

2. jcchurch posted this