Created
August 22, 2012 19:42
Revisions
-
aspyct revised this gist
Aug 22, 2012 . 1 changed file with 81 additions and 81 deletions.There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal 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 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 "f", 6 h.push "a", 1 h.push "j", 10 h.push "i", 9 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 end -
aspyct created this gist
Aug 22, 2012 .There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal 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