Class: DS::BinaryHeap

Inherits:
CompleteBinaryTree show all
Defined in:
lib/ds/trees/binary_heap.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

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