# Source code for skfmm.heap

```
from .pheap import pheap as _pheap
# This wrapper exists only to add docstrings to the heap class.
# Cython cannot do this automatically at the time of writing.
# see: http://docs.cython.org/src/userguide/special_methods.html
[docs]class heap(object):
""".. note::
Using this class is not required to use
:py:func:`distance`, :py:func:`travel_time` or
:py:func:`extension_velocities`. It is provided for
experimenting with fast marching algorithms.
This class implements a binary min heap (or heap queue) to support
the fast marching algorithm. A min heap is a list which has the
property that the smallest element is always the first element.
http://en.wikipedia.org/wiki/Binary_heap
This class differs from the heap queue (:py:obj:`heapq`) in the
Python standard library because it supports changing the value of
elements in the heap and maintains forward and backward ids.
The fast marching method uses this data structure to track
elements in the solution narrow band. The fast marching method
needs to know which element in the narrow band is nearest the zero
level-set at each iteration. When a new point enters the solution
narrow band the element is added to the heap.
New elements (an address and an initial value) are added to the
heap with the :py:meth:`push` method. The :py:meth:`push` method
returns an integer (a :py:obj:`heap_id`) which is used to update
the value of the element.
As the solution evolves, the distance of points already in the heap
are updated via the :py:meth:`update` method. The
:py:meth:`update` method takes the :py:obj:`heap_id` returned by the
:py:meth:`push` along with a new distance value.
The smallest element is taken off the heap with the :py:meth:`pop`
method. The address and value of the top element is returned.
The constructor for heap needs to know the number of elements that
will enter the heap.
>>> from skfmm import heap
>>> h = heap(10)
>>> h.push(10,0.2)
0
>>> h.push(11,0.3)
1
>>> h.push(12,0.1)
2
>>> h.peek()
0.1
>>> h.update(1, 0.01)
>>> h.peek()
0.01
>>> h.pop()
(11, 0.01)
>>> h.pop()
(12, 0.1)
>>> h.pop()
(10, 0.2)
>>> assert h.empty()
"""
def __init__(self, max_size, self_test=False):
"""Create a new min heap.
Parameters
----------
max_heap : int
The maximum size of the heap.
self_test : Boolean
If True a consistency check is made after each
heap operation. This is used in testing and
results in a slower calculation.
"""
self._heap = _pheap(max_size, self_test)
[docs] def push(self, addr, value):
"""Add a value to the heap, give an address and a value.
Parameters
----------
addr : int
An id number which is returned when the element is
popped off the heap.
value : float
An initial numerical value for this element.
Returns
-------
heap_id : int
An id number into the heap used to update
the value of this element. The value of a
point in the heap can be updated by calling
:py:meth:`update` with this id and a new value.
"""
return self._heap._push(addr, value)
[docs] def pop(self):
"""Remove and return the address and value of the top element on the
heap.
Returns
-------
(addr, value) : tuple
A tuple of the address given when the element
was pushed onto the heap and the current value
of the element.
"""
return self._heap._pop()
[docs] def update(self, heap_id, value):
"""Update the value of a point already in the heap, the heap ordering
is updated.
Parameters
----------
heap_id : int
The :py:obj:`heap_id` value returned by
:py:meth:`push` when this element was added to the
heap.
value : float
The new value for this element.
"""
self._heap._set(heap_id, value)
[docs] def empty(self):
"""
Returns
-------
empty : Boolean
True if the heap is empty.
"""
return self._heap._empty()
[docs] def peek(self):
"""
Returns the top (smallest) value on the heap without removing it.
Returns
-------
value : float
The top (smallest) value on the heap.
"""
return self._heap._peek()
```