BinaryHeap(initial_capacity=128)The number of values in the heap
The number of levels in the binary heap (see Notes below). The values are stored in the last level, so 2**levels is the capacity of the heap before another resize is required.
The minimum number of levels in the heap (relates to the :None:None:`initial_capacity` parameter.)
A binary heap is an object to store values in, optimized in such a way that the minimum (or maximum, but a minimum in this implementation) value can be found in O(log2(N)) time. In this implementation, a reference value (a single integer) can also be stored with each value.
Use the methods push() and pop() to put in or extract values. In C, use the corresponding push_fast() and pop_fast().
This implementation stores the binary heap in an array twice as long as the number of elements in the heap. The array is structured in levels, starting at level 0 with a single value, doubling the amount of values in each level. The final level contains the actual values, the level before it contains the pairwise minimum values. The level before that contains the pairwise minimum values of that level, etc. Take a look at this illustration:
level: 0 11 2222 33333333 4444444444444444 index: 0 12 3456 78901234 5678901234567890 1 2 3
The actual values are stored in level 4. The minimum value of position 15
and 16 is stored in position 7. min(17,18)->8, min(7,8)->3, min(3,4)->1. When adding a value, only the path to the top has to be updated, which takesO(log2(N)) time.
The advantage of this implementation relative to more common
implementations that swap values when pushing to the array is that data only needs to be swapped once when an element is removed. This means that keeping an array of references along with the values is very inexpensive. Th disadvantage is that if you pop the minimum value, the tree has to be traced from top to bottom and back. So if you only want values and no references, this implementation will probably be slower. If you need references (and maybe cross references to be kept up to date) this implementation will be faster.
Estimate of the size of the heap, if known in advance. (In any case, the heap will dynamically grow and shrink as required, though never below the :None:None:`initial_capacity`.)
A binary heap class that can store values and an integer reference.
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them