Skip to content

Instantly share code, notes, and snippets.

@aspyct
Created August 22, 2012 19:42

Revisions

  1. aspyct revised this gist Aug 22, 2012. 1 changed file with 81 additions and 81 deletions.
    162 changes: 81 additions & 81 deletions heap.rb
    Original file line number Diff line number Diff line change
    @@ -1,98 +1,98 @@
    class Heap
    def initialize
    # @elements is an array representing the tree
    # for each i:
    # parent => @elements[i / 2]
    # left => @elements[i * 2]
    # right => @elements[i * 2 + 1]
    @elements = []
    end

    def empty
    return @elements.count == 0
    end

    def pop_min
    value = @elements[0].first

    # Replace the [0]th element with the last one and bubble it down
    pair = @elements.pop

    # If it was the last element of the array, abort anyway
    if @elements.count > 0
    @elements[0] = pair
    self.bubble_down pair, 0
    end

    return value
    end

    def peek_min
    return @elements[0].first
    end

    def push(object, order)
    # Put the element at the end of the array and bubble it up the tree
    offset = @elements.count
    pair = [object, order]
    @elements << pair

    self.bubble_up pair, offset
    end

    def bubble_up(pair, offset)
    # Push an element up the tree, if need be
    parent = offset / 2

    while (offset > 0 && @elements[parent].last > pair.last)
    @elements[parent], @elements[offset] = @elements[offset], @elements[parent]
    offset = parent
    parent = offset / 2
    end
    end

    def bubble_down(pair, offset)
    # Push an element down the tree if need be
    while (offset < @elements.count / 2)
    offset_a = offset * 2
    offset_b = offset_a + 1

    if @elements[offset_a].last > @elements[offset_b].last
    smallest = offset_b
    else
    smallest = offset_a
    end

    if pair.last <= @elements[smallest].last
    break
    end

    @elements[offset], @elements[smallest] = @elements[smallest], @elements[offset]
    offset = smallest
    end
    end
    def initialize
    # @elements is an array representing the tree
    # for each i:
    # parent => @elements[i / 2]
    # left => @elements[i * 2]
    # right => @elements[i * 2 + 1]
    @elements = []
    end

    def empty
    return @elements.count == 0
    end

    def pop_min
    value = @elements[0].first

    # Replace the [0]th element with the last one and bubble it down
    pair = @elements.pop

    # If it was the last element of the array, abort anyway
    if @elements.count > 0
    @elements[0] = pair
    self.bubble_down pair, 0
    end

    return value
    end

    def peek_min
    return @elements[0].first
    end

    def push(object, order)
    # Put the element at the end of the array and bubble it up the tree
    offset = @elements.count
    pair = [object, order]
    @elements << pair

    self.bubble_up pair, offset
    end

    def bubble_up(pair, offset)
    # Push an element up the tree, if need be
    parent = offset / 2

    while (offset > 0 && @elements[parent].last > pair.last)
    @elements[parent], @elements[offset] = @elements[offset], @elements[parent]
    offset = parent
    parent = offset / 2
    end
    end

    def bubble_down(pair, offset)
    # Push an element down the tree if need be
    while (offset < @elements.count / 2)
    offset_a = offset * 2
    offset_b = offset_a + 1

    if @elements[offset_a].last > @elements[offset_b].last
    smallest = offset_b
    else
    smallest = offset_a
    end

    if pair.last <= @elements[smallest].last
    break
    end

    @elements[offset], @elements[smallest] = @elements[smallest], @elements[offset]
    offset = smallest
    end
    end
    end

    h = Heap.new

    # Insert 'a' => 'o' in the heap, random order
    h.push "g", 7
    h.push "m", 13
    h.push "k", 11
    h.push "d", 4
    h.push "c", 3
    h.push "n", 14
    h.push "b", 2
    h.push "g", 7
    h.push "j", 10
    h.push "f", 6
    h.push "e", 5
    h.push "a", 1
    h.push "k", 11
    h.push "h", 8
    h.push "m", 13
    h.push "o", 15
    h.push "j", 10
    h.push "i", 9
    h.push "c", 3
    h.push "e", 5
    h.push "o", 15
    h.push "h", 8
    h.push "l", 12

    # Dump the heap
    while !h.empty
    puts h.pop_min
    puts h.pop_min
    end
  2. aspyct created this gist Aug 22, 2012.
    98 changes: 98 additions & 0 deletions heap.rb
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,98 @@
    class Heap
    def initialize
    # @elements is an array representing the tree
    # for each i:
    # parent => @elements[i / 2]
    # left => @elements[i * 2]
    # right => @elements[i * 2 + 1]
    @elements = []
    end

    def empty
    return @elements.count == 0
    end

    def pop_min
    value = @elements[0].first

    # Replace the [0]th element with the last one and bubble it down
    pair = @elements.pop

    # If it was the last element of the array, abort anyway
    if @elements.count > 0
    @elements[0] = pair
    self.bubble_down pair, 0
    end

    return value
    end

    def peek_min
    return @elements[0].first
    end

    def push(object, order)
    # Put the element at the end of the array and bubble it up the tree
    offset = @elements.count
    pair = [object, order]
    @elements << pair

    self.bubble_up pair, offset
    end

    def bubble_up(pair, offset)
    # Push an element up the tree, if need be
    parent = offset / 2

    while (offset > 0 && @elements[parent].last > pair.last)
    @elements[parent], @elements[offset] = @elements[offset], @elements[parent]
    offset = parent
    parent = offset / 2
    end
    end

    def bubble_down(pair, offset)
    # Push an element down the tree if need be
    while (offset < @elements.count / 2)
    offset_a = offset * 2
    offset_b = offset_a + 1

    if @elements[offset_a].last > @elements[offset_b].last
    smallest = offset_b
    else
    smallest = offset_a
    end

    if pair.last <= @elements[smallest].last
    break
    end

    @elements[offset], @elements[smallest] = @elements[smallest], @elements[offset]
    offset = smallest
    end
    end
    end

    h = Heap.new

    # Insert 'a' => 'o' in the heap, random order
    h.push "d", 4
    h.push "n", 14
    h.push "b", 2
    h.push "g", 7
    h.push "j", 10
    h.push "f", 6
    h.push "e", 5
    h.push "a", 1
    h.push "k", 11
    h.push "h", 8
    h.push "m", 13
    h.push "o", 15
    h.push "i", 9
    h.push "c", 3
    h.push "l", 12

    # Dump the heap
    while !h.empty
    puts h.pop_min
    end