Class: DataStructuresRMolinari::Heap

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

Overview

TODO:

  • let caller see the priority of the top element. Maybe this is useful sometimes.

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(item, priority)

    • add a new item 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(item, priority)

    • 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.

The internal requirements needed to implement update have several consequences.

  • Items added to the heap must be distinct. Otherwise we would not know which occurrence to update

  • There is some bookkeeping overhead.

If client code doesn’t need to call update then we can create a “non-addressable” heap that allows for the insertion of duplicate items and has slightly faster runtime overall. See the arguments to the initializer.

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

Constant Summary

Constants included from Shared

Shared::INFINITY

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Shared

#contains_duplicates?

Constructor Details

#initialize(max_heap: false, addressable: true, debug: false) ⇒ Heap

Returns a new instance of Heap.

Parameters:

  • max_heap (defaults to: false) —

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

  • addressable (defaults to: true) —

    when truthy, the heap is addressable. This means that

    • item priorities are updatable with update(item, p), and

    • items added to the heap must be distinct.

    When falsy, priorities are not updateable but items may be inserted multiple times. Operations are slightly faster because there is less internal bookkeeping.

  • debug (defaults to: false) —

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



64
65
66
67
68
69
70
71
 
# File 'lib/data_structures_rmolinari/heap.rb', line 64

def initialize(max_heap: false, addressable: true, debug: false)
  @data = []
  @size = 0
  @max_heap = max_heap
  @addressable = addressable
  @index_of = {} # used in addressable heaps
  @debug = debug
end

Instance Attribute Details

#size ⇒ Object (readonly)

The number of items currently in the heap



51
52
53
 
# File 'lib/data_structures_rmolinari/heap.rb', line 51

def size
  @size
end

Instance Method Details

#empty? ⇒ Boolean

Is the heap empty?

Returns:

  • (Boolean) 


74
75
76
 
# File 'lib/data_structures_rmolinari/heap.rb', line 74

def empty?
  @size.zero?
end

#insert(value, priority) ⇒ Object

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

Parameters:

  • value —

    the item to be inserted.

    • If the heap is addressible (the default) it is an error to insert an item that is already present in the heap.

  • priority —

    the priority to use for new item. The values used as priorities must be totally ordered via <=>.

Raises:



82
83
84
85
86
87
88
89
90
91
 
# File 'lib/data_structures_rmolinari/heap.rb', line 82

def insert(value, priority)
  raise DataError, "Heap already contains #{value}" if @addressable && contains?(value)

  @size += 1

  d = InternalPair.new(value, priority)
  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:

  • a value with minimal priority (maximal for max-heaps). 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 and they do not appear at the top of the heap in any guaranteed order.



105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/data_structures_rmolinari/heap.rb', line 105

def pop
  result = top
  assign(@data[@size], root)

  @data[@size] = nil
  @size -= 1
  @index_of.delete(result) if @addressable

  sift_down(root) if @size.positive?

  result
end

#top ⇒ Object

Return the top of the heap without removing it

Returns:

  • a value with minimal priority (maximal for max-heaps). 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 and they do not appear at the top of the heap in any guaranteed order.



97
98
99
100
101
 
# File 'lib/data_structures_rmolinari/heap.rb', line 97

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

  @data[root].item
end

#update(element, priority) ⇒ Object

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

Raises:



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/data_structures_rmolinari/heap.rb', line 123

def update(element, priority)
  raise LogicError, 'Cannot update priorities in a non-addressable heap' unless @addressable
  raise DataError, "Cannot update priority for value #{element} not already in the heap" unless contains?(element)

  idx = @index_of[element]
  old = @data[idx].priority
  @data[idx].priority = priority
  if less_than_priority?(old, priority)
    sift_down(idx)
  elsif less_than_priority?(priority, old)
    sift_up(idx)
  end

  check_heap_property if @debug
end