Class: BinaryHeap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/rb_binary_heap.rb

Instance Method Summary collapse

Constructor Details

#initialize(array = [], type: nil, compare_attribute: nil, &block) ⇒ BinaryHeap

Returns a new instance of BinaryHeap.



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/rb_binary_heap.rb', line 6

def initialize(array = [], type: nil, compare_attribute: nil, &block)
  @array = array

  comparison_method_name = :compare

  if block_given?
    if type || compare_attribute
      raise 'Heap: :type and :compare_attribute should not be defined if the block is given'
    end

    define_singleton_method(comparison_method_name) do |a, b|
      block.call a, b
    end
  else
    type = :min if type.nil?

    op = heap_type_to_comparison_operator type

    if compare_attribute.nil?
      define_singleton_method(comparison_method_name) do |a, b|
        a.send(op, b)
      end
    else
      define_singleton_method(comparison_method_name) do |a, b|
        a_value = a.send(compare_attribute)
        b_value = b.send(compare_attribute)
        a_value.send(op, b_value)
      end
    end
  end

  heapify
end

Instance Method Details

#each ⇒ Object 



71
72
73
 
# File 'lib/rb_binary_heap.rb', line 71

def each
  yield pop while not_empty?
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


67
68
69
 
# File 'lib/rb_binary_heap.rb', line 67

def empty?
  @array.empty?
end

#not_empty? ⇒ Boolean

Returns:

  • (Boolean) 


63
64
65
 
# File 'lib/rb_binary_heap.rb', line 63

def not_empty?
  !empty?
end

#pop ⇒ Object 



51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/rb_binary_heap.rb', line 51

def pop
  raise "Heap: Can't pop, heap is empty" if @array.empty?
  return @array.pop if @array.size == 1

  result = @array.first
  last_element = @array.pop
  @array[0] = last_element
  
  sift_down_from_first
  result
end

#push(value) ⇒ Object 



45
46
47
48
49
 
# File 'lib/rb_binary_heap.rb', line 45

def push(value)
  @array.push value
  sift_up_from_last
  self
end

#size ⇒ Object 



75
76
77
 
# File 'lib/rb_binary_heap.rb', line 75

def size
  @array.size
end

#top ⇒ Object 



40
41
42
43
 
# File 'lib/rb_binary_heap.rb', line 40

def top
  raise "Heap: Can't get the top element, heap is empty" if @array.empty?
  @array.first
end