Description

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.

Reference

  <quote>
  Cormen1990: Chapter 7 (Heapsort) of 'An introduction to algorithms', by
  Cormen, T.H; Leiserson, C.E.; Rivest, R.L; MIT Press, Cambridge, 1990
  ISBN 0-262-53091-0
  </quote>

Author(s)

Renald Buter (buter at cwts nl)

Thanks

Special thanks to Nenad Ocelic for many suggestions.

Methods

cmp_idx heapify inherited internal_size left new parent pop push push_all right size sort sort_internal swap to_s top

Classes and Modules

Class Heap::EmptyHeapException
Class Heap::Max
Class Heap::Min

Constants

VERSION = '1.0.0'

Public Class methods

inherited(sub)

We are an abstract class

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

Public Instance methods

pop()

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

push(elm)

Push an element on the heap.

push_all(elms)

Push a list of elements on the heap.

size()

Get the heap size

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!

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+.

to_s()

Pretty print

top()

Get the first (maximum) element on the heap

Protected Instance methods

cmp_idx(i,j)

Compare elements at the supplied indices

heapify(i)

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

internal_size()

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

left(i)

Get the node left of node i >= 0

parent(i)

Get the parent of the node i > 0.

right(i)

Get the node right of node i >= 0

swap(i,j)

Swap elements in the array