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)
Methods
Classes and Modules
Class Heap::EmptyHeapException
Class Heap::Max
Class Heap::Min
Public Class methods
inherited(sub) [ source ]

We are an abstract class

new(array) [ source ]

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() [ source ]

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

push(elm) [ source ]

Push an element on the heap.

push_all(elms) [ source ]

Push a list of elements on the heap.

size() [ source ]

Get the heap size

sort() [ source ]

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() [ source ]

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() [ source ]

Pretty print

top() [ source ]

Get the first (maximum) element on the heap