Class: HeapInternal

Inherits:
Object
  • Object
show all
Includes:
Shared::BinaryTreeArithmetic
Defined in:
lib/data_structures_rmolinari/heap_internal.rb

Overview

TODO:

  • relax the requirement that priorities must be comparable vai < and respond to negation. Instead, allow comparison via <=> and handle max-heaps differently.

    • this will allow priorities to be arrays for tie-breakers and similar.

A heap is a balanced binary tree in which each entry has an associated priority. For each node p of the tree that isn’t the root, the priority of the element at p is not less than the priority of the element at the parent of p.

Thus the priority at each node p - root or not - is no greater than the priorities of the elements in the subtree rooted at p. It is a “min-heap”.

We can make it a max-heap, in which each node’s priority is no greater than the priority of its parent, via a parameter to the initializer.

We provide the following operations

  • empty?

    • is the heap empty?

    • O(1)

  • insert

    • add a new element to the heap with an associated priority

    • O(log N)

  • top

    • return the lowest-priority element, which is the element at the root of the tree. In a max-heap this is the highest-priority element.

    • O(1)

  • pop

    • removes and returns the item that would be returned by top

    • O(log N)

  • update

    • tell the heap that the priority of a particular item has changed

    • O(log N)

Here N is the number of elements in the heap.

References:

  • en.wikipedia.org/wiki/Binary_heap

  • Edelkamp, S., Elmasry, A., Katajainen, J., _Optimizing Binary Heaps_, Theory Comput Syst (2017), vol 61, pp 606-636, DOI 10.1007/s00224-017-9760-2

Defined Under Namespace

Classes: Pair

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(max_heap: false, debug: false) ⇒ HeapInternal

Returns a new instance of HeapInternal.

Parameters:

  • max_heap (defaults to: false) —

    when truthy, make a max-heap rather than a min-heap

  • debug (defaults to: false) —

    when truthy, verify the heap property after each update than might violate it. This makes operations much slower.



51
52
53
54
55
56
57
 
# File 'lib/data_structures_rmolinari/heap_internal.rb', line 51

def initialize(max_heap: false, debug: false)
  @data = []
  @size = 0
  @max_heap = max_heap
  @index_of = {}
  @debug = debug
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



45
46
47
 
# File 'lib/data_structures_rmolinari/heap_internal.rb', line 45

def size
  @size
end

Instance Method Details

#empty? ⇒ Boolean

Is the heap empty?

Returns:

  • (Boolean) 


60
61
62
 
# File 'lib/data_structures_rmolinari/heap_internal.rb', line 60

def empty?
  @size.zero?
end

#insert(value, priority) ⇒ Object

TODO:

  • check for duplicate

Insert a new element into the heap with the given property.

Parameters:

  • value —

    the item to be inserted. It is an error to insert an item that is already present in the heap, though we don’t check for this.

  • priority —

    the priority to use for new item. The values used as priorities ust be totally ordered via < and, if self is a max-heap, must respond to negation @- in the natural order-respecting way.



71
72
73
74
75
76
77
78
79
80
 
# File 'lib/data_structures_rmolinari/heap_internal.rb', line 71

def insert(value, priority)
  priority *= -1 if @max_heap

  @size += 1

  d = Pair.new(priority, value)
  assign(d, @size)

  sift_up(@size)
end

#pop ⇒ Object

Return the top of the heap and remove it, updating the structure to maintain the necessary properties.

Returns:

  • the value with minimal (maximal for max-heaps) priority. Strictly speaking, it returns the item at the root of the binary tree; this element has minimal priority, but there may be other elements with the same priority.



93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/data_structures_rmolinari/heap_internal.rb', line 93

def pop
  result = top
  @index_of.delete(result)

  assign(@data[@size], root)

  @data[@size] = nil
  @size -= 1

  sift_down(root) if @size.positive?

  result
end

#top ⇒ Object

Return the top of the heap without removing it

Returns:

  • the value with minimal (maximal for max-heaps) priority. Strictly speaking, it returns the item at the root of the binary tree; this element has minimal priority, but there may be other elements with the same priority.



85
86
87
88
89
 
# File 'lib/data_structures_rmolinari/heap_internal.rb', line 85

def top
  raise 'Heap is empty!' unless @size.positive?

  @data[root].item
end

#update(element, priority) ⇒ Object

TODO:

  • check that the element is in the heap

Update the priority of the given element and maintain the necessary heap properties.

Parameters:

  • element —

    the item whose priority we are updating. It is an error to update the priority of an element not already in the heap

  • priority —

    the new priority



114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/data_structures_rmolinari/heap_internal.rb', line 114

def update(element, priority)
  priority *= -1 if @max_heap

  idx = @index_of[element]
  old = @data[idx].priority
  @data[idx].priority = priority
  if priority > old
    sift_down(idx)
  elsif priority < old
    sift_up(idx)
  end

  check_heap_property if @debug
end