Class: DS::BinaryHeap
- Inherits:
-
CompleteBinaryTree
- Object
- CompleteBinaryTree
- DS::BinaryHeap
- Defined in:
- lib/ds/trees/binary_heap.rb
Instance Attribute Summary collapse
-
#data ⇒ Object
Returns the value of attribute data.
Instance Method Summary collapse
-
#heapify(i) ⇒ Object
Maintain heap condition for i node.
-
#heapify! ⇒ Object
Arranges data in heap.
-
#initialize(*args, &block) ⇒ BinaryHeap
constructor
Create new Heap from args.
-
#insert(value) ⇒ Object
Inserts new value to heap maintaining the heap relation.
- #relation(parent, child) ⇒ Object
- #set_relation(&relation) ⇒ Object
- #to_a ⇒ Object
Methods inherited from CompleteBinaryTree
#<<, #children, #left, #left_index, #parent, #parent_index, #right, #right_index, #root
Constructor Details
#initialize(*args, &block) ⇒ BinaryHeap
Create new Heap from args. Given block sets the heap relation. Default heap relation is Max Heap.
7 8 9 10 11 12 13 14 15 |
# File 'lib/ds/trees/binary_heap.rb', line 7 def initialize(*args, &block) if block_given? @relation = block else @relation = Proc.new{|parent,child| parent >= child} end @data = args.to_a heapify! end |
Instance Attribute Details
#data ⇒ Object
Returns the value of attribute data.
3 4 5 |
# File 'lib/ds/trees/binary_heap.rb', line 3 def data @data end |
Instance Method Details
#heapify(i) ⇒ Object
Maintain heap condition for i node. O(log)
51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
# File 'lib/ds/trees/binary_heap.rb', line 51 def heapify(i) left = left_index(i) left = nil if left >= @data.size right = right_index(i) right = nil if right >= @data.size largest = [i,left,right].compact.sort{|x,y| relation(x,y)?-1:1}.first if largest != i @data[i], @data[largest] = @data[largest], @data[i] heapify(largest) end end |
#heapify! ⇒ Object
Arranges data in heap. O(n)
27 28 29 30 31 |
# File 'lib/ds/trees/binary_heap.rb', line 27 def heapify! (@data.size/2).downto(0) do |i| heapify(i) end end |
#insert(value) ⇒ Object
Inserts new value to heap maintaining the heap relation. Returns heap itself. O(log)
36 37 38 39 40 41 42 43 44 45 46 47 |
# File 'lib/ds/trees/binary_heap.rb', line 36 def insert(value) @data.push value child = @data.size-1 parent = parent_index(child) while parent >= 0 and !relation(parent,child) @data[child], @data[parent] = @data[parent], @data[child] child = parent parent = parent_index(child) end self end |
#relation(parent, child) ⇒ Object
21 22 23 |
# File 'lib/ds/trees/binary_heap.rb', line 21 def relation(parent,child) @relation.call(@data[parent],@data[child]) end |
#set_relation(&relation) ⇒ Object
17 18 19 |
# File 'lib/ds/trees/binary_heap.rb', line 17 def set_relation(&relation) @relation = relation end |
#to_a ⇒ Object
66 67 68 |
# File 'lib/ds/trees/binary_heap.rb', line 66 def to_a @data end |