Class: RubyDataStructures::MaxHeap

Inherits:
Array
  • Object
show all
Defined in:
lib/RubyDataStructures/max_heap.rb

Constant Summary collapse

Infinity = 
1.0/0

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#heapsize ⇒ Object

Returns the value of attribute heapsize.



4
5
6
 
# File 'lib/RubyDataStructures/max_heap.rb', line 4

def heapsize
  @heapsize
end

Class Method Details

.build(array) ⇒ Object

Builds a max-heap from an array



33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/RubyDataStructures/max_heap.rb', line 33

def self.build(array)
  heap = self.new(array)
  heap.heapsize = array.size

  if heap.heapsize > 0
    ((heap.heapsize/2) - 1).downto(0) do |i|
      heap.max_heapify!(i)
    end
  end

  return heap
end

Instance Method Details

#extract_maximum! ⇒ Object

Extracts the maximum of the heap and max_heapifies the remaining heap. Returns the maximum of the input heap



53
54
55
56
57
58
59
60
61
62
 
# File 'lib/RubyDataStructures/max_heap.rb', line 53

def extract_maximum!
  raise "Heap Underflow - The heap is empty" if self.heapsize < 1

  max_value = self[0]
  self[0] = self[self.heapsize - 1]
  self.heapsize = self.heapsize - 1
  self.max_heapify!(0)

  return max_value
end

#increase_key!(i, key) ⇒ Object 



64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/RubyDataStructures/max_heap.rb', line 64

def increase_key!(i, key)
  raise "New key is smaller than the current key" if key < self[i]

  self[i] = key
  while (i > 0) && (self[parent(i)] < self[i])
    exchange(i, parent(i))
    i = parent(i)
  end

  return self
end

#insert!(key) ⇒ Object 



76
77
78
79
80
 
# File 'lib/RubyDataStructures/max_heap.rb', line 76

def insert!(key)
  self.heapsize = self.heapsize + 1
  self[self.heapsize  - 1] = -Infinity
  self.increase_key!(self.heapsize - 1, key)
end

#max_heapify!(i) ⇒ Object

It is assumed that the binary trees rooted at left(i) and right(i) are max heaps, but self might be smaller than its children, thus violating the max-heap property. max_heapify! lets the value at self float down in the max-heap, so that the subtree rooted at index i obeys the max-heap property



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/RubyDataStructures/max_heap.rb', line 10

def max_heapify!(i)
  l = left(i)
  r = right(i)

  if l < self.heapsize && self[l] > self[i]
    largest = l
  else
    largest = i
  end

  if r < self.heapsize && self[r] > self[largest]
    largest = r
  end

  if largest != i
    exchange(i, largest)
    max_heapify!(largest)
  end

  return self
end

#maximum ⇒ Object

Returns the maximum element of the heap



47
48
49
 
# File 'lib/RubyDataStructures/max_heap.rb', line 47

def maximum
  return self[0]
end