Class: BinHeap

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(&prc) ⇒ BinHeap

Returns a new instance of BinHeap.



4
5
6
7
 
# File 'lib/bin_heap.rb', line 4

def initialize(&prc)
  @store = Array.new
  @prc = prc || Proc.new { |el1, el2| el1 <=> el2 }
end

Instance Attribute Details

#store ⇒ Object

Returns the value of attribute store.



2
3
4
 
# File 'lib/bin_heap.rb', line 2

def store
  @store
end

Class Method Details

.find_children(last_idx, parent_idx) ⇒ Object 



77
78
79
80
81
82
83
 
# File 'lib/bin_heap.rb', line 77

def self.find_children(last_idx, parent_idx)
  child1 = (parent_idx * 2) + 1
  child2 = (parent_idx * 2) + 2


  return [child1, child2].select{ |idx| idx <= last_idx }
end

.find_parent(child_idx) ⇒ Object 



85
86
87
88
89
90
91
 
# File 'lib/bin_heap.rb', line 85

def self.find_parent(child_idx)
  if child_idx == 0 
    raise "Out of bounds"
  else
    return (child_idx - 1) / 2 
  end
end

.heapify_down(store, parent_idx, &prc) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/bin_heap.rb', line 47

def self.heapify_down(store, parent_idx, &prc)
  prc = prc || Proc.new { |el1, el2| el1 <=> el2 }      
  
  children_idx = find_children(store.length - 1, parent_idx)
  
  c0_idx = children_idx[0]
  c1_idx = children_idx[1]

  children = []
  children << store[c0_idx] if c0_idx
  children << store[c1_idx] if c1_idx

  parent = store[parent_idx]

  #When the parent index is where it's supposed to be
  if children.all? { |child| prc.call(child, parent) >= 0}
    return store
  end

  if store.length == 1
    swap_idx = c0_idx
  else
    swap_idx = prc.call(children[0], children[1]) == 1 ? c1_idx : c0_idx
  end

  store[swap_idx], store[parent_idx] = parent, store[swap_idx]

  heapify_down(store, swap_idx, &prc)
end

.heapify_up(store, child_idx, &prc) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/bin_heap.rb', line 33

def self.heapify_up(store, child_idx, &prc)
  prc = prc || Proc.new { |el1, el2| el1 <=> el2 }      
  return store if child_idx == 0 

  parent_idx = find_parent(child_idx)
  
  if prc.call(store[child_idx], store[parent_idx]) == -1
    store[child_idx], store[parent_idx] = store[parent_idx], store[child_idx]
    heapify_up(store, parent_idx, &prc)
  else
    return store
  end
end

Instance Method Details

#extract ⇒ Object 



14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
# File 'lib/bin_heap.rb', line 14

def extract
  raise "Heap is empty" if @store.empty?

  top_priority = @store[0]
  
  if @store.length > 1
    @store[0] = @store.pop
    self.class.heapify_down(@store, 0, &@prc)
  else
    @store.pop
  end
  
  top_priority  
end

#insert(value) ⇒ Object 



9
10
11
12
 
# File 'lib/bin_heap.rb', line 9

def insert(value)
  @store << value
  self.class.heapify_up(@store, @store.length - 1, &@prc)
end