Class: DSA::MaxHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/dsa-ruby/heap.rb

Overview

DSA::MaxHeap - A max-heap (priority queue) data structure.

The largest element is always at the root. Provides O(log n) insertion and extraction of the maximum element.

Examples:

heap = DSA::MaxHeap.new([5, 3, 7, 1])
heap.pop   # => 7
heap.peek  # => 5

Instance Method Summary collapse

Constructor Details

#initialize(elements = []) ⇒ DSA::MaxHeap

Initialize a new max-heap with optional initial elements.

Examples:

DSA::MaxHeap.new([3, 1, 2])

Parameters:

  • elements (Array<Comparable>) (defaults to: []) —

    optional array of elements to heapify



156
157
158
159
 
# File 'lib/dsa-ruby/heap.rb', line 156

def initialize(elements = [])
  @elements = []
  elements.each { |e| push(e) }
end

Instance Method Details

#empty? ⇒ Boolean

Checks if the heap is empty.

Examples:

heap = DSA::MaxHeap.new
heap.empty?  # => true

Returns:

  • (Boolean) —

    true if the heap contains no elements



217
218
219
 
# File 'lib/dsa-ruby/heap.rb', line 217

def empty?
  @elements.empty?
end

#peek ⇒ Comparable

Returns the maximum element without removing it.

Examples:

heap.push(5).push(1).push(3)
heap.peek  # => 5

Returns:

  • (Comparable) —

    the maximum element

Raises:

  • (IndexError) —

    if the heap is empty



196
197
198
199
 
# File 'lib/dsa-ruby/heap.rb', line 196

def peek
  raise IndexError, "heap is empty" if empty?
  @elements[0]
end

#pop ⇒ Comparable

Removes and returns the maximum element from the heap.

Examples:

heap.push(5).push(1).push(3)
heap.pop  # => 5

Returns:

  • (Comparable) —

    the maximum element

Raises:

  • (IndexError) —

    if the heap is empty



180
181
182
183
184
185
186
187
 
# File 'lib/dsa-ruby/heap.rb', line 180

def pop
  raise IndexError, "heap is empty" if empty?

  swap(0, @elements.size - 1)
  max = @elements.pop
  sift_down(0)
  max
end

#push(val) ⇒ DSA::MaxHeap

Inserts an element into the heap.

Examples:

heap.push(5).push(3).push(1)

Parameters:

  • val (Comparable) —

    the value to insert

Returns:



167
168
169
170
171
 
# File 'lib/dsa-ruby/heap.rb', line 167

def push(val)
  @elements << val
  sift_up(@elements.size - 1)
  self
end

#size ⇒ Integer

Returns the number of elements in the heap.

Examples:

heap.push(5).push(3)
heap.size  # => 2

Returns:

  • (Integer) —

    the number of elements



207
208
209
 
# File 'lib/dsa-ruby/heap.rb', line 207

def size
  @elements.size
end

#to_a ⇒ Array<Comparable>

Returns a defensive copy of the heap as an array.

Examples:

heap.push(5).push(3).push(1)
heap.to_a  # => [5, 3, 1] (may vary based on internal structure)

Returns:

  • (Array<Comparable>) —

    an array containing all elements (not in sorted order)



227
228
229
 
# File 'lib/dsa-ruby/heap.rb', line 227

def to_a
  @elements.dup
end