Class: Polyrun::Partition::MinHeap

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

Overview

Binary min-heap of [load, shard_index] for LPT placement (tie-break: lower shard index).

Instance Method Summary collapse

Constructor Details

#initialize ⇒ MinHeap

Returns a new instance of MinHeap.



5
6
7
 
# File 'lib/polyrun/partition/min_heap.rb', line 5

def initialize
  @a = []
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


24
25
26
 
# File 'lib/polyrun/partition/min_heap.rb', line 24

def empty?
  @a.empty?
end

#pop_min ⇒ Object 



14
15
16
17
18
19
20
21
22
 
# File 'lib/polyrun/partition/min_heap.rb', line 14

def pop_min
  return nil if @a.empty?

  min = @a[0]
  last = @a.pop
  @a[0] = last if @a.any?
  sift_down(0) if @a.size > 1
  min
end

#push(load, shard_index) ⇒ Object 



9
10
11
12
 
# File 'lib/polyrun/partition/min_heap.rb', line 9

def push(load, shard_index)
  @a << [load.to_f, Integer(shard_index)]
  sift_up(@a.size - 1)
end