Class: OfflineSort::FixedSizeMinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/offline_sort/fixed_size_min_heap.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(array, &sort_by) ⇒ FixedSizeMinHeap

Returns a new instance of FixedSizeMinHeap.



8
9
10
11
12
13
14
 
# File 'lib/offline_sort/fixed_size_min_heap.rb', line 8

def initialize(array, &sort_by)
  @array = array
  @sort_by = sort_by || Proc.new { |item| item }
  @size_limit = array.size
  @heap_end = array.size - 1
  ((array.size * 0.5) - 1).to_i.downto(0) { |i| heapify(i) }
end

Instance Attribute Details

#array ⇒ Object

Returns the value of attribute array.



3
4
5
 
# File 'lib/offline_sort/fixed_size_min_heap.rb', line 3

def array
  @array
end

#heap_end ⇒ Object (readonly)

Returns the value of attribute heap_end.



6
7
8
 
# File 'lib/offline_sort/fixed_size_min_heap.rb', line 6

def heap_end
  @heap_end
end

#size_limit ⇒ Object (readonly)

Returns the value of attribute size_limit.



5
6
7
 
# File 'lib/offline_sort/fixed_size_min_heap.rb', line 5

def size_limit
  @size_limit
end

#sort_by ⇒ Object (readonly)

Returns the value of attribute sort_by.



4
5
6
 
# File 'lib/offline_sort/fixed_size_min_heap.rb', line 4

def sort_by
  @sort_by
end

Instance Method Details

#pop ⇒ Object 



22
23
24
25
26
27
28
 
# File 'lib/offline_sort/fixed_size_min_heap.rb', line 22

def pop
  item = array[0]
  array[0] = array[heap_end]
  heapify(0)
  shrink_heap unless item.nil?
  item
end

#push(item) ⇒ Object 



16
17
18
19
20
 
# File 'lib/offline_sort/fixed_size_min_heap.rb', line 16

def push(item)
  grow_heap
  array[heap_end] = item
  sift_up(heap_end)
end