Binary Heap Module

heap_module.rb

module HeapModule
  def self.sort(keys)
    sort!(keys.clone)
  end
 
  def self.sort!(keys)
    build_max_heap(keys)
    (keys.size-1).downto(1) do |i|
      keys[0], keys[i] = keys[i], keys[0]
      max_heapify(keys, i, 0)
    end
    keys
  end
 
  def self.build_max_heap(keys)
    (keys.size/2-1).downto(0) do |i|
      max_heapify(keys, keys.size, i)
    end
    keys
  end
 
  def self.max_heapify(keys, size, i)
    l = 2*i+1
    r = 2*i+2
    if l < size and keys[l] > keys[i]
      largest = l 
    else 
      largest = i
    end
    if r < size and keys[r] > keys[largest]
      largest = r 
    end
    if (largest != i)
      keys[i], keys[largest] = keys[largest], keys[i]
      max_heapify(keys, size, largest)
    end
  end

  def self.extract_maximum(keys)
    raise "Empty array." if keys.empty?
    max = keys[0]
    keys[0] = keys[keys.length-1]
    keys.pop
    max_heapify(keys,keys.length-1,0)
    max
  end
  
  def self.heap_increase_key(keys,i,key)
    raise "New key is lower than the current one" if key < keys[i]
    keys[i] = key
    while i > 1 and keys[(i/2).to_i] < keys[i]
      keys[i] = keys[(i/2).to_i]
      keys[(i/2).to_i] = keys[i]
      i = (i/2).to_i
    end
  end

end