Class: DS::BinaryHeap

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

Instance Attribute Summary collapse

Class Method 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

Class Method Details

.max(*args) ⇒ Object

Create new Maximum Heap from args.



18
19
20
 
# File 'lib/ds/trees/binary_heap.rb', line 18

def BinaryHeap.max(*args)
  new(*args){|parent,child| parent >= child}
end

.min(*args) ⇒ Object

Create new Minimum Heap from args.



23
24
25
 
# File 'lib/ds/trees/binary_heap.rb', line 23

def BinaryHeap.min(*args)
  new(*args){|parent,child| parent < child}
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


93
94
95
 
# File 'lib/ds/trees/binary_heap.rb', line 93

def empty?
  @data.empty?
end

#heapify(i) ⇒ Object

Maintains heap condition for i node. O(log)



43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/ds/trees/binary_heap.rb', line 43

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)



35
36
37
38
39
 
# File 'lib/ds/trees/binary_heap.rb', line 35

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)



72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/ds/trees/binary_heap.rb', line 72

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

#length ⇒ Object Also known as: size 



87
88
89
 
# File 'lib/ds/trees/binary_heap.rb', line 87

def length
  @data.size 
end

#relation(parent, child) ⇒ Object

Evaluates Heap relation.



29
30
31
 
# File 'lib/ds/trees/binary_heap.rb', line 29

def relation(parent,child)
  @relation.call(@data[parent],@data[child])
end

#shift ⇒ Object

Removes element from heap maintaining heap relation.



59
60
61
62
63
64
65
66
67
 
# File 'lib/ds/trees/binary_heap.rb', line 59

def shift
  if @data.size > 0
    result = @data.shift
    return result if @data.size.zero?
    @data.unshift @data.pop
    heapify(0)
  end
  result
end

#to_a ⇒ Object 



97
98
99
 
# File 'lib/ds/trees/binary_heap.rb', line 97

def to_a
  @data
end