Heap

A simple Heap structure and sort.

Extending Heap

To extend the heap, implement a cmp(i,j) method which compares array elements i and j and returns true iff i is larger than j, where larger or is the required heap sorting. See Heap::Min and Heap::Max for examples.

Notes

The parent, left and right methods do not check the supplied parameter, but their result is only valid if the supplied with an integer >=0 for left and right and >0 for parent.

Methods
Classes and Modules
Class Heap::EmptyHeapException
Class Heap::Max
Class Heap::Min
Public Class methods
inherited(sub)

We are an abstract class

[ show source ]

# File lib/facets/more/heap.rb, line 63
  def self.inherited(sub) sub.class_eval("public_class_method :new") end
new(array)

Initialise the heap. If supplied an array, build the heap with the values of the array. The array can be unsorted. Note: this method can only be called by superclasses

[ show source ]

# File lib/facets/more/heap.rb, line 86
  def initialize(array)
    @array, @heap_size = array, array.length
    ((@heap_size * 0.5) - 1).downto(0) { |i| heapify(i) }
  end
Public Instance methods
pop()

Extract the first element from the heap. Will raise EmptyHeapException if there are no (more) elements on the heap.

[ show source ]

# File lib/facets/more/heap.rb, line 134
  def pop
    raise EmptyHeapException if @heap_size < 1
    @heap_size -= 1
    top, @array[0] = @array[0], @array[@heap_size]
    heapify(0)
    top
  end
push(elm)

Push an element on the heap.

[ show source ]

# File lib/facets/more/heap.rb, line 143
  def push(elm)
    i = @heap_size
    @heap_size += 1
    while i > 0 and cmp(elm, @array[(j = parent(i))])
      @array[i] = @array[(i = j)]
    end
    @array[i] = elm
  end
push_all(elms)

Push a list of elements on the heap.

[ show source ]

# File lib/facets/more/heap.rb, line 153
  def push_all(elms)
    elms.each {|e| push(e)}
  end
size()

Get the heap size

[ show source ]

# File lib/facets/more/heap.rb, line 92
  def size
    @heap_size
  end
sort()

Heap-sort a clone of the internal array. This will not touch the internal array. Returns the array sorted reversely on the heap condition!

[ show source ]

# File lib/facets/more/heap.rb, line 104
  def sort
    old_ary = @array.dup
    old_heap = @heap_size
    new_ary = sort_internal
    @array = old_ary
    @heap_size = old_heap
    new_ary
  end
sort_internal()

Heap-sort the internal array. This reduces heap size to 1, since sorting the internal array destroys the heap property. Use this only if the heap is not used after this call and you want save speed and memory; otherwise use Heap#sort. See +Heap#sort+.

[ show source ]

# File lib/facets/more/heap.rb, line 117
  def sort_internal
    (@array.length-1).downto(1) do |i|
      swap(0,i)
      @heap_size -= 1
      heapify(0)
    end
    @array
  end
to_s()

Pretty print

[ show source ]

# File lib/facets/more/heap.rb, line 97
  def to_s
    "<#{self.class}: size=#@heap_size, top=#{self.top}>"
  end
top()

Get the first (maximum) element on the heap

[ show source ]

# File lib/facets/more/heap.rb, line 127
  def top
    raise EmptyHeapException if @heap_size < 1
    @array[0]
  end
Protected Instance methods
cmp_idx(i,j)

Compare elements at the supplied indices

[ show source ]

# File lib/facets/more/heap.rb, line 160
  def cmp_idx(i,j) 
    cmp(@array[i], @array[j]) 
  end
heapify(i)

Keeps an heap sorted with the smallest (largest) element on top

[ show source ]

# File lib/facets/more/heap.rb, line 180
  def heapify(i)
    l = left i
    top = if l < @heap_size && cmp_idx(l,i) then l else i end
    r = right i
    top = if r < @heap_size && cmp_idx(r,top) then r else top end
    if top != i
      swap(i, top)
      heapify(top)
    end
  end
internal_size()

Get the size of the internal array. This may be different from the heap size, e.g. after sort has been called.

[ show source ]

# File lib/facets/more/heap.rb, line 193
  def internal_size
    @array.size
  end
left(i)

Get the node left of node i >= 0

[ show source ]

# File lib/facets/more/heap.rb, line 170
  def left(i)
    ( i << 1 ) + 1  # 2i+1
  end
parent(i)

Get the parent of the node i > 0.

[ show source ]

# File lib/facets/more/heap.rb, line 165
  def parent(i)
    ( i - 1 ) >> 1  # (i-1)/2, only valid iff i > 0 !!
  end
right(i)

Get the node right of node i >= 0

[ show source ]

# File lib/facets/more/heap.rb, line 175
  def right(i)
    ( i << 1 ) + 2  # 2i+2
  end
swap(i,j)

Swap elements in the array

[ show source ]

# File lib/facets/more/heap.rb, line 198
  def swap(i,j)
    @array[i], @array[j] = @array[j], @array[i]
  end