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) 


26
27
28
 
# File 'lib/data_structures/heap.rb', line 26

def empty?
  @store.empty?
end

#extract ⇒ Object 



56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/data_structures/heap.rb', line 56

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 



71
72
73
74
75
 
# File 'lib/data_structures/heap.rb', line 71

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) 


77
78
79
 
# File 'lib/data_structures/heap.rb', line 77

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

#insert(el) ⇒ Object 



39
40
41
42
43
44
45
46
47
48
 
# File 'lib/data_structures/heap.rb', line 39

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) 


50
51
52
53
54
 
# File 'lib/data_structures/heap.rb', line 50

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 



22
23
24
 
# File 'lib/data_structures/heap.rb', line 22

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

#length ⇒ Object 



30
31
32
 
# File 'lib/data_structures/heap.rb', line 30

def length
  @store.length
end

#merge(other_heap) ⇒ Object

Raises:

  • (ArgumentError) 


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

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 



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

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

#to_s ⇒ Object 



18
19
20
 
# File 'lib/data_structures/heap.rb', line 18

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