scipy.cluster._hierarchy:Heap

Extended Summary

Heap stores values and keys. Values are passed explicitly, whereas keys are assigned implicitly to natural numbers (from 0 to n - 1).

The supported operations (all have O(log n) time complexity):

• Return the current minimum value and the corresponding key.

• Remove the current minimum value.

• Change the value of the given key. Note that the key must be still in the heap.

The heap is stored as an array, where children of parent i have indices 2 * i + 1 and 2 * i + 2. All public methods are based on sift_down and sift_up methods, which restore the heap property by moving an element down or up in the heap.