Class: Winloop::MinHeap

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

Overview

A tiny binary min-heap keyed on the node’s #deadline. Enough for timers.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ MinHeap

Returns a new instance of MinHeap.



449
450
451
 
# File 'lib/winloop/scheduler.rb', line 449

def initialize
  @a = []
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


453
 
# File 'lib/winloop/scheduler.rb', line 453

def empty? = @a.empty?

#peek ⇒ Object 



455
 
# File 'lib/winloop/scheduler.rb', line 455

def peek = @a[0]

#pop ⇒ Object 



469
470
471
472
473
474
475
476
477
478
 
# File 'lib/winloop/scheduler.rb', line 469

def pop
  return nil if @a.empty?
  top = @a[0]
  last = @a.pop
  unless @a.empty?
    @a[0] = last
    sift_down(0)
  end
  top
end

#push(node) ⇒ Object 



457
458
459
460
461
462
463
464
465
466
467
 
# File 'lib/winloop/scheduler.rb', line 457

def push(node)
  @a << node
  i = @a.size - 1
  while i > 0
    parent = (i - 1) / 2
    break if @a[parent].deadline <= @a[i].deadline
    @a[parent], @a[i] = @a[i], @a[parent]
    i = parent
  end
  node
end

#size ⇒ Object 



454
 
# File 'lib/winloop/scheduler.rb', line 454

def size = @a.size