Class: MinHeap

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

Instance Method Summary collapse

Constructor Details

#initialize(comparator = lambda { |x, y| x <=> y }) ⇒ MinHeap

Returns a new instance of MinHeap.



2
3
4
5
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 2

def initialize(comparator = lambda { |x, y| x <=> y })
    @comparator = comparator
    @items = []
end

Instance Method Details

#decrease(index, delta) ⇒ Object 



28
29
30
31
32
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 28

def decrease(index, delta)
    item_index = find_item_index(index)
    @items[item_index][0] -= delta
    update(item_index)
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


54
55
56
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 54

def empty?
    @items.empty?
end

#find_item_index(index) ⇒ Object

def find_item(index)

@items.find { |item| item.last == index }

end



50
51
52
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 50

def find_item_index(index)
    @items.find_index { |item| item.last == index }
end

#increase(index, delta) ⇒ Object 



34
35
36
37
38
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 34

def increase(index, delta)
    item_index = find_item_index(index)
    @items[item_index][0] += delta
    update(item_index)
end

#order ⇒ Object 



58
59
60
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 58

def order
    @items.sort.map(&:last)
end

#peak ⇒ Object 



17
18
19
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 17

def peak
    @items[0]
end

#pop ⇒ Object 



12
13
14
15
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 12

def pop
    @items[0], @items[@items.size-1] = @items[@items.size-1], @items[0]
    @items.pop.tap { sink_down(0) }
end

#push(x) ⇒ Object 



7
8
9
10
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 7

def push(x)
    @items.push(x)
    swim_up(@items.size-1)
end

#replace(index, val) ⇒ Object 



40
41
42
43
44
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 40

def replace(index, val)
    item_index = find_item_index(index)
    @items[item_index][0] = val
    update(item_index)
end

#update(item_index) ⇒ Object 



21
22
23
24
25
26
 
# File 'lib/multi_dbs_load_balancer/min_heap.rb', line 21

def update(item_index)
    return if item_index < 0 || item_index >= @items.size

    swim_up(item_index)
    sink_down(item_index)
end