Class: DS::BinaryHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/ds/trees/binary_heap.rb

Overview

Create new Heap from args.

Direct Known Subclasses

IndexedBinaryHeap

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*args, &block) ⇒ BinaryHeap

Create new Heap from args. Given block sets the heap relation. Default heap relation is Max Heap.



8
9
10
11
12
13
14
15
16
 
# File 'lib/ds/trees/binary_heap.rb', line 8

def initialize(*args, &block)
  @relation = if block_given?
                block
              else
                -> (parent, child) { parent >= child }
              end
  @store = HeapStore.new(*args)
  heapify!
end

Instance Attribute Details

#store ⇒ Object (readonly)

Returns the value of attribute store.



4
5
6
 
# File 'lib/ds/trees/binary_heap.rb', line 4

def store
  @store
end

Class Method Details

.max(*args) ⇒ Object

Create new Maximum Heap from args.



19
20
21
 
# File 'lib/ds/trees/binary_heap.rb', line 19

def self.max(*args)
  new(*args) { |parent, child| parent >= child }
end

.min(*args) ⇒ Object

Create new Minimum Heap from args.



24
25
26
 
# File 'lib/ds/trees/binary_heap.rb', line 24

def self.min(*args)
  new(*args) { |parent, child| parent < child }
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


69
70
71
 
# File 'lib/ds/trees/binary_heap.rb', line 69

def empty?
  store.empty?
end

#heapify! ⇒ Object

Arranges data in heap. O(n)



35
36
37
 
# File 'lib/ds/trees/binary_heap.rb', line 35

def heapify!
  (length / 2).downto(1) { |i| sink(i) }
end

#insert(value) ⇒ Object

Inserts new value to heap maintaining the heap relation. Returns heap itself. O(log)



53
54
55
56
57
 
# File 'lib/ds/trees/binary_heap.rb', line 53

def insert(value)
  store.push value
  swim(length)
  self
end

#length ⇒ Object Also known as: size 



63
64
65
 
# File 'lib/ds/trees/binary_heap.rb', line 63

def length
  store.length
end

#relation(parent, child) ⇒ Object

Evaluates Heap relation.



29
30
31
 
# File 'lib/ds/trees/binary_heap.rb', line 29

def relation(parent, child)
  @relation.call(store[parent], store[child])
end

#shift ⇒ Object

Removes element from heap maintaining heap relation.



40
41
42
43
44
45
46
47
48
 
# File 'lib/ds/trees/binary_heap.rb', line 40

def shift
  unless empty?
    result = store.first
    swap(1, length)
    store.pop
    sink(1)
  end
  result
end

#to_a ⇒ Object 



73
74
75
 
# File 'lib/ds/trees/binary_heap.rb', line 73

def to_a
  store.to_a
end

#top ⇒ Object 



59
60
61
 
# File 'lib/ds/trees/binary_heap.rb', line 59

def top
  store.first
end