Class: Heap

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

Overview

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.

Note

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

  • Renald Buter (buter at cwts nl)

Thanks

Special thanks to Nenad Ocelic for many suggestions.

Copyright © 2002,2004 Renald Buter (Ruby Version)

See Cormen1990 for original

Ruby License…

History

$Id: heap.rb,v 1.0 2004/11/30 transami Exp $

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



77
78
79
80
 
# File 'lib/carat/heap.rb', line 77

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 



54
 
# File 'lib/carat/heap.rb', line 54

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:



125
126
127
128
129
130
131
 
# File 'lib/carat/heap.rb', line 125

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.



134
135
136
137
138
139
140
141
 
# File 'lib/carat/heap.rb', line 134

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.



144
145
146
 
# File 'lib/carat/heap.rb', line 144

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

#size ⇒ Object

Get the heap size



83
84
85
 
# File 'lib/carat/heap.rb', line 83

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!



95
96
97
98
99
100
101
102
 
# File 'lib/carat/heap.rb', line 95

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.



108
109
110
111
112
113
114
115
 
# File 'lib/carat/heap.rb', line 108

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



88
89
90
 
# File 'lib/carat/heap.rb', line 88

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

#top ⇒ Object

Get the first (maximum) element on the heap

Raises:



118
119
120
121
 
# File 'lib/carat/heap.rb', line 118

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