Class: DSA::MinHeap

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

Overview

DSA::MinHeap - A min-heap (priority queue) data structure.

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

Examples:

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

# Or build incrementally with chained pushes:
heap = DSA::MinHeap.new
heap.push(5).push(3).push(7).push(1)

Instance Method Summary collapse

Constructor Details

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

Initialize a new min-heap with optional initial elements.

Examples:

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

Parameters:

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

    optional array of elements to heapify



21
22
23
24
 
# File 'lib/dsa-ruby/heap.rb', line 21

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

Instance Method Details

#empty? ⇒ Boolean

Checks if the heap is empty.

Examples:

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

Returns:

  • (Boolean) —

    true if the heap contains no elements



82
83
84
 
# File 'lib/dsa-ruby/heap.rb', line 82

def empty?
  @elements.empty?
end

#peek ⇒ Comparable

Returns the minimum element without removing it.

Examples:

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

Returns:

  • (Comparable) —

    the minimum element

Raises:

  • (IndexError) —

    if the heap is empty



61
62
63
64
 
# File 'lib/dsa-ruby/heap.rb', line 61

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

#pop ⇒ Comparable

Removes and returns the minimum element from the heap.

Examples:

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

Returns:

  • (Comparable) —

    the minimum element

Raises:

  • (IndexError) —

    if the heap is empty



45
46
47
48
49
50
51
52
 
# File 'lib/dsa-ruby/heap.rb', line 45

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

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

#push(val) ⇒ DSA::MinHeap

Inserts an element into the heap.

Examples:

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

Parameters:

  • val (Comparable) —

    the value to insert

Returns:



32
33
34
35
36
 
# File 'lib/dsa-ruby/heap.rb', line 32

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



72
73
74
 
# File 'lib/dsa-ruby/heap.rb', line 72

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  # => [1, 3, 5] (may vary based on internal structure)

Returns:

  • (Array<Comparable>) —

    an array containing all elements (not in sorted order)



92
93
94
 
# File 'lib/dsa-ruby/heap.rb', line 92

def to_a
  @elements.dup
end