class OfflineSort::FixedSizeMinHeap
Attributes
array[RW]
heap_end[R]
size_limit[R]
sort_by[R]
Public Class Methods
new(array, &sort_by)
click to toggle source
# 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
Public Instance Methods
pop()
click to toggle source
# 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)
click to toggle source
# 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
Private Instance Methods
compare(i, j)
click to toggle source
Compare elements at the supplied indices
# File lib/offline_sort/fixed_size_min_heap.rb, line 44 def compare(i, j) (sort_by.call(array[i]) <=> sort_by.call(array[j])) == -1 end
grow_heap()
click to toggle source
# File lib/offline_sort/fixed_size_min_heap.rb, line 37 def grow_heap raise "Heap Size (#{size_limit}) Exceeded" if heap_end == (size_limit - 1) @heap_end += 1 end
heapify(i)
click to toggle source
Keeps an heap sorted with the smallest (largest) element on top
# File lib/offline_sort/fixed_size_min_heap.rb, line 71 def heapify(i) l = left(i) top = (l <= heap_end) && compare(l, i) ? l : i r = right(i) top = (r <= heap_end) && compare(r, top) ? r : top if top != i swap(i, top) heapify(top) end end
left(i)
click to toggle source
Get the node left of node i >= 0
# File lib/offline_sort/fixed_size_min_heap.rb, line 61 def left(i) (2 * i) + 1 end
parent(i)
click to toggle source
Get the parent of the node i > 0.
# File lib/offline_sort/fixed_size_min_heap.rb, line 56 def parent(i) (i - 1) / 2 end
right(i)
click to toggle source
Get the node right of node i >= 0
# File lib/offline_sort/fixed_size_min_heap.rb, line 66 def right(i) (2 * i) + 2 end
shrink_heap()
click to toggle source
# File lib/offline_sort/fixed_size_min_heap.rb, line 32 def shrink_heap array[heap_end] = nil @heap_end -= 1 end
sift_up(i)
click to toggle source
# File lib/offline_sort/fixed_size_min_heap.rb, line 84 def sift_up(i) if i > 0 p = parent(i) if p && compare(i, p) swap(i, p) sift_up(p) end end end
swap(i, j)
click to toggle source
Swap elements in the array
# File lib/offline_sort/fixed_size_min_heap.rb, line 49 def swap(i, j) temp = array[i] array[i] = array[j] array[j] = temp end