Class: Containers::MinHeap

Inherits:
Heap
  • Object
show all
Defined in:
lib/containers/heap.rb

Overview

A MinHeap is a heap where the items are returned in ascending order of key value.

Instance Method Summary collapse

Methods inherited from Heap

#change_key, #clear, #delete, #empty?, #has_key?, #merge!, #next, #next_key, #pop, #push, #size

Constructor Details

#initialize(ary = []) ⇒ MinHeap

call-seq:

MinHeap.new(ary) -> new_heap

Creates a new MinHeap with an optional array parameter of items to insert into the heap. A MinHeap is created by calling Heap.new { |x, y| (x <=> y) == -1 }, so this is a convenience class.

minheap = MinHeap.new([1, 2, 3, 4])
minheap.pop #=> 1
minheap.pop #=> 2



466
467
468
 
# File 'lib/containers/heap.rb', line 466

def initialize(ary=[])
  super(ary) { |x, y| (x <=> y) == -1 }
end

Instance Method Details

#min ⇒ Object

call-seq:

min -> value
min -> nil

Returns the item with the smallest key, but does not remove it from the heap.

minheap = MinHeap.new([1, 2, 3, 4])
minheap.min #=> 1



478
479
480
 
# File 'lib/containers/heap.rb', line 478

def min
  self.next
end

#min! ⇒ Object

call-seq:

min! -> value
min! -> nil

Returns the item with the smallest key and removes it from the heap.

minheap = MinHeap.new([1, 2, 3, 4])
minheap.min! #=> 1
minheap.size #=> 3



491
492
493
 
# File 'lib/containers/heap.rb', line 491

def min!
  self.pop
end