data_structures.heap.randomized_heap

Attributes

T

Classes

RandomizedHeap	A data structure that allows inserting a new value and to pop the smallest
RandomizedHeapNode	One node of the randomized heap. Contains the value and references to

Module Contents

class data_structures.heap.randomized_heap.RandomizedHeap(data: collections.abc.Iterable[T] | None = ())

Bases: Generic[T]

A data structure that allows inserting a new value and to pop the smallest values. Both operations take O(logN) time where N is the size of the structure. Wiki: https://en.wikipedia.org/wiki/Randomized_meldable_heap

>>> RandomizedHeap([2, 3, 1, 5, 1, 7]).to_sorted_list()
[1, 1, 2, 3, 5, 7]

>>> rh = RandomizedHeap()
>>> rh.pop()
Traceback (most recent call last):
    ...
IndexError: Can't get top element for the empty heap.

>>> rh.insert(1)
>>> rh.insert(-1)
>>> rh.insert(0)
>>> rh.to_sorted_list()
[-1, 0, 1]

__bool__() → bool

Check if the heap is not empty.

>>> rh = RandomizedHeap()
>>> bool(rh)
False
>>> rh.insert(1)
>>> bool(rh)
True
>>> rh.clear()
>>> bool(rh)
False

clear() → None

Clear the heap.

>>> rh = RandomizedHeap([3, 1, 3, 7])
>>> rh.clear()
>>> rh.pop()
Traceback (most recent call last):
    ...
IndexError: Can't get top element for the empty heap.

insert(value: T) → None

Insert the value into the heap.

>>> rh = RandomizedHeap()
>>> rh.insert(3)
>>> rh.insert(1)
>>> rh.insert(3)
>>> rh.insert(7)
>>> rh.to_sorted_list()
[1, 3, 3, 7]

pop() → T | None

Pop the smallest value from the heap and return it.

>>> rh = RandomizedHeap([3, 1, 3, 7])
>>> rh.pop()
1
>>> rh.pop()
3
>>> rh.pop()
3
>>> rh.pop()
7
>>> rh.pop()
Traceback (most recent call last):
    ...
IndexError: Can't get top element for the empty heap.

to_sorted_list() → list[Any]

Returns sorted list containing all the values in the heap.

>>> rh = RandomizedHeap([3, 1, 3, 7])
>>> rh.to_sorted_list()
[1, 3, 3, 7]

top() → T

Return the smallest value from the heap.

>>> rh = RandomizedHeap()
>>> rh.insert(3)
>>> rh.top()
3
>>> rh.insert(1)
>>> rh.top()
1
>>> rh.insert(3)
>>> rh.top()
1
>>> rh.insert(7)
>>> rh.top()
1

_root: RandomizedHeapNode[T] | None = None

class data_structures.heap.randomized_heap.RandomizedHeapNode(value: T)

Bases: Generic[T]

One node of the randomized heap. Contains the value and references to two children.

static merge(root1: RandomizedHeapNode[T] | None, root2: RandomizedHeapNode[T] | None) → RandomizedHeapNode[T] | None

Merge 2 nodes together.

>>> rhn1 = RandomizedHeapNode(10)
>>> rhn2 = RandomizedHeapNode(20)
>>> RandomizedHeapNode.merge(rhn1, rhn2).value
10

>>> rhn1 = RandomizedHeapNode(20)
>>> rhn2 = RandomizedHeapNode(10)
>>> RandomizedHeapNode.merge(rhn1, rhn2).value
10

>>> rhn1 = RandomizedHeapNode(5)
>>> rhn2 = RandomizedHeapNode(0)
>>> RandomizedHeapNode.merge(rhn1, rhn2).value
0

_value: T

left: RandomizedHeapNode[T] | None = None

right: RandomizedHeapNode[T] | None = None

property value: T

Return the value of the node.

>>> rhn = RandomizedHeapNode(10)
>>> rhn.value
10
>>> rhn = RandomizedHeapNode(-10)
>>> rhn.value
-10

data_structures.heap.randomized_heap.T