Class: Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/rb_heap/heap.rb,
lib/rb_heap/sort.rb,
lib/rb_heap/version.rb

Constant Summary collapse

VERSION = 
"1.1.0"

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(compare_symbol = :<, storage = [], &compare_fn) ⇒ Heap

Returns a new instance of Heap.



2
3
4
5
6
 
# File 'lib/rb_heap/heap.rb', line 2

def initialize(compare_symbol = :<, storage = [], &compare_fn)
  @heap = storage
  @size = 0
  initialize_compare(compare_symbol, &compare_fn)
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



8
9
10
 
# File 'lib/rb_heap/heap.rb', line 8

def size
  @size
end

Class Method Details

.invertComparison(order, &compare_fn) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/rb_heap/sort.rb', line 17

def self.invertComparison(order, &compare_fn)
  if block_given?
    lambda{|a, b| not compare_fn.call(a, b)}
  elsif order == :< or order.nil?
    lambda{|a, b| a > b}
  elsif order == :>
    lambda{|a, b| a < b}
  else
    raise ArgumentError.new("The comparison symbol needs to be either :> or :<")
  end
end

.sort(array, order = :<, &compare_fn) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
# File 'lib/rb_heap/sort.rb', line 2

def self.sort(array, order = :<, &compare_fn)
  compare_fn = self.invertComparison(order, &compare_fn)
  heap = Heap.new(order, array, &compare_fn)

  array.each do |element|
    heap.add(element)
  end

  (0...array.size).reverse_each do |i|
    array[i] = heap.pop
  end

  heap.to_a
end

Instance Method Details

#add(element) ⇒ Object Also known as: << 



34
35
36
37
38
39
 
# File 'lib/rb_heap/heap.rb', line 34

def add(element)
  @heap[@size] = element
  @size += 1
  rebalance_up(size - 1)
  self
end

#clear ⇒ Object 



58
59
60
61
 
# File 'lib/rb_heap/heap.rb', line 58

def clear
  @heap = []
  @size = 0
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


10
11
12
 
# File 'lib/rb_heap/heap.rb', line 10

def empty?
  size == 0
end

#offer(element) ⇒ Object 



48
49
50
51
52
53
54
55
56
 
# File 'lib/rb_heap/heap.rb', line 48

def offer(element)
  if compare(peak, element)
    result = peak
    replace(element)
    result
  else
    element
  end
end

#peak ⇒ Object 



14
15
16
 
# File 'lib/rb_heap/heap.rb', line 14

def peak
  @heap[0]
end

#pop ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/rb_heap/heap.rb', line 18

def pop
  result = peak

  if size > 1
    @size -= 1
    @heap[0] = @heap[@size]
    rebalance_down(0)
  else
    @size = 0
  end

  @heap[@size] = nil

  result
end

#replace(element) ⇒ Object 



43
44
45
46
 
# File 'lib/rb_heap/heap.rb', line 43

def replace(element)
  @heap[0] = element
  rebalance_down(0)
end

#to_a ⇒ Object 



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

def to_a
  @heap.reject{|element| element.nil? }
end