Class: Graphos::BinaryHeap

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

Defined Under Namespace

Classes: KeyVal

Instance Method Summary collapse

Constructor Details

#initialize(&compare) ⇒ BinaryHeap

Returns a new instance of BinaryHeap.



3
4
5
6
7
8
 
# File 'lib/graphos/binary_heap.rb', line 3

def initialize &compare
  @compare = compare
  @indexes = []
  @keys = []
  @values = []
end

Instance Method Details

#change(key, new_value) ⇒ Object 



26
27
28
29
30
31
32
33
 
# File 'lib/graphos/binary_heap.rb', line 26

def change key, new_value
  if has_key? key
    @values[key] = new_value
    parent_val = @values[parent(@indexes[key])]
    move_up key
    heapify key
  end
end

#has_key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


16
17
18
 
# File 'lib/graphos/binary_heap.rb', line 16

def has_key? key
  @indexes[key] != nil
end

#next ⇒ Object 



20
21
22
23
24
 
# File 'lib/graphos/binary_heap.rb', line 20

def next
  if key = @keys.first
    key_val key
  end
end

#ordered ⇒ Object 



56
57
 
# File 'lib/graphos/binary_heap.rb', line 56

def ordered
end

#pop ⇒ Object 



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/graphos/binary_heap.rb', line 35

def pop
  return nil if size == 0

  result = key_val(@keys.first)
  @indexes[result.key] = nil
  @values[result.key] = nil

  last = @keys.pop
  if size > 0
    @keys[0] = last 
    @indexes[last] = 0
    heapify last
  end

  result
end

#push(key, value) ⇒ Object 



10
11
12
13
14
 
# File 'lib/graphos/binary_heap.rb', line 10

def push key, value
  if !has_key? key
    insert key, value
  end
end

#size ⇒ Object 



52
53
54
 
# File 'lib/graphos/binary_heap.rb', line 52

def size
  @keys.size
end