Module: Heapify::ArrayExtension

Defined in:
lib/heapify.rb

Overview

Provides a heapify method for arrays. It also provides methods for adding and removing elements from the heap.

Instance Method Summary collapse

Instance Method Details

#heap_pop ⇒ Object?

Remove the minimum element from the heap.

O(log n) time complexity.



34
35
36
37
38
39
40
41
 
# File 'lib/heapify.rb', line 34

def heap_pop
  return if empty?

  swap(0, size - 1)
  min = pop
  heapify_down(0)
  min
end

#heap_push(val) ⇒ void

This method returns an undefined value.

Add an element to the heap.

O(log n) time complexity.



24
25
26
27
 
# File 'lib/heapify.rb', line 24

def heap_push(val)
  self << val
  heapify_up(size - 1)
end

#heapify ⇒ Array

Transforms an array into a heap, in-place, in linear time.



11
12
13
14
15
16
 
# File 'lib/heapify.rb', line 11

def heapify
  (size / 2).downto(0) do |i|
    heapify_down(i)
  end
  self
end