Class: Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/data_structures/heap.rb

Direct Known Subclasses

PriorityQueue

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Heap

Returns a new instance of Heap.



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

def initialize
  @store = []
end

Class Method Details

.from_array(array) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
 
# File 'lib/data_structures/heap.rb', line 2

def self.from_array(array)
  heap = Heap.new
  heap.instance_variable_set(:@store, array)

  heap.send(:store).length.downto(0).each do |idx|
    children_indices = heap.send(:children_indices, idx)
    heap.send(:heapify_down, idx, children_indices) unless children_indices.empty?
  end

  heap
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


36
37
38
 
# File 'lib/data_structures/heap.rb', line 36

def empty?
  @store.empty?
end

#extract ⇒ Object 



66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/data_structures/heap.rb', line 66

def extract
  return nil if @store.empty?
  return @store.shift if @store.length <= 2

  @store[0], @store[-1] = @store[-1], @store[0]
  head = @store.pop

  el_idx = 0
  children_indices = children_indices(el_idx)

  heapify_down(el_idx, children_indices) unless children_indices.empty?

  head
end

#find(el) ⇒ Object 



81
82
83
84
85
 
# File 'lib/data_structures/heap.rb', line 81

def find(el)
  return nil if @store.empty? || el < @store.first
  @store.each { |store_el| return store_el if store_el == el }
  nil
end

#include?(el) ⇒ Boolean

Returns:

  • (Boolean) 


87
88
89
 
# File 'lib/data_structures/heap.rb', line 87

def include?(el)
  @store.include?(el)
end

#insert(el) ⇒ Object 



49
50
51
52
53
54
55
56
57
58
 
# File 'lib/data_structures/heap.rb', line 49

def insert(el)
  @store << el

  el_idx = @store.length - 1
  parent_idx = parent_idx(el_idx)

  heapify_up(el_idx, parent_idx)

  el
end

#insert_mutliple(arr) ⇒ Object

Raises:

  • (ArgumentError) 


60
61
62
63
64
 
# File 'lib/data_structures/heap.rb', line 60

def insert_mutliple(arr)
  raise ArgumentError.new("Can only insert multiple elements via an Array. You passed a #{arr.class}.") unless arr.is_a?(Array)
  array = self.send(:store) + arr
  self.class.from_array(array)
end

#inspect ⇒ Object 



32
33
34
 
# File 'lib/data_structures/heap.rb', line 32

def inspect
  "Heap: head=#{self.peek || 'nil'}, length=#{self.length}"
end

#length ⇒ Object 



40
41
42
 
# File 'lib/data_structures/heap.rb', line 40

def length
  @store.length
end

#merge(other_heap) ⇒ Object

Raises:

  • (ArgumentError) 


91
92
93
94
95
 
# File 'lib/data_structures/heap.rb', line 91

def merge(other_heap)
  raise ArgumentError.new("May only merge with a Heap. You passed a #{other_heap.class}.") unless other_heap.is_a?(Heap)
  array = self.send(:store) + other_heap.send(:store)
  self.class.from_array(array)
end

#peek ⇒ Object 



44
45
46
47
 
# File 'lib/data_structures/heap.rb', line 44

def peek
  return nil if @store.empty?
  @store.first
end

#to_a ⇒ Object 



18
19
20
21
22
23
24
25
26
 
# File 'lib/data_structures/heap.rb', line 18

def to_a
  arr = []
  copy = self.dup
  copy.instance_variable_set(:@store, @store.dup)
  until copy.empty?
    arr << copy.extract
  end
  arr
end

#to_s ⇒ Object 



28
29
30
 
# File 'lib/data_structures/heap.rb', line 28

def to_s
  "Heap: head=#{self.peek || 'nil'}, length=#{self.length}"
end