Class: Heap

Inherits:
Object show all
Defined in:
lib/mega/heap.rb

Overview

:title: 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.

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)

Direct Known Subclasses

Max, Min

Defined Under Namespace

Classes: EmptyHeapException, Max, Min

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(array) ⇒ Heap

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



92
93
94
95
 
# File 'lib/mega/heap.rb', line 92

def initialize(array)
  @array, @heap_size = array, array.length
  (@heap_size/2 - 1).downto(0) { |i| heapify(i) }
end

Class Method Details

.inherited(sub) ⇒ Object 



69
 
# File 'lib/mega/heap.rb', line 69

def self.inherited(sub) sub.class_eval("public_class_method :new") end

Instance Method Details

#pop ⇒ Object

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

Raises:



140
141
142
143
144
145
146
 
# File 'lib/mega/heap.rb', line 140

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) ⇒ Object

Push an element on the heap.



149
150
151
152
153
154
155
156
 
# File 'lib/mega/heap.rb', line 149

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) ⇒ Object

Push a list of elements on the heap.



159
160
161
 
# File 'lib/mega/heap.rb', line 159

def push_all(elms)
  elms.each {|e| push(e)}
end

#size ⇒ Object

Get the heap size



98
99
100
 
# File 'lib/mega/heap.rb', line 98

def size
  @heap_size
end

#sort ⇒ Object

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



110
111
112
113
114
115
116
117
 
# File 'lib/mega/heap.rb', line 110

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 ⇒ Object

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.



123
124
125
126
127
128
129
130
 
# File 'lib/mega/heap.rb', line 123

def sort_internal
  (@array.length-1).downto(1) do |i|
    swap(0,i)
    @heap_size -= 1
    heapify(0)
  end
  @array
end

#to_s ⇒ Object

Pretty print



103
104
105
 
# File 'lib/mega/heap.rb', line 103

def to_s
  "<#{self.class}: size=#@heap_size, top=#{self.top}>"
end

#top ⇒ Object

Get the first (maximum) element on the heap

Raises:



133
134
135
136
 
# File 'lib/mega/heap.rb', line 133

def top
  raise EmptyHeapException if @heap_size < 1
  @array[0]
end