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