Class: Containers::MaxHeap

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

Overview

A MaxHeap is a heap where the items are returned in descending 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 = []) ⇒ MaxHeap

call-seq:

MaxHeap.new(ary) -> new_heap

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

maxheap = MaxHeap.new([1, 2, 3, 4])
maxheap.pop #=> 4
maxheap.pop #=> 3

432
433
434
# File 'lib/containers/heap.rb', line 432

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

Instance Method Details

#maxObject

call-seq:

max -> value
max -> nil

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

maxheap = MaxHeap.new([1, 2, 3, 4])
maxheap.max #=> 4

444
445
446
# File 'lib/containers/heap.rb', line 444

def max
  self.next
end

#max!Object

call-seq:

max! -> value
max! -> nil

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

maxheap = MaxHeap.new([1, 2, 3, 4])
maxheap.max! #=> 4
maxheap.size #=> 3

457
458
459
# File 'lib/containers/heap.rb', line 457

def max!
  self.pop
end