data_structures.heap.skew_heap

Attributes

T

Classes

SkewHeap	A data structure that allows inserting a new value and to pop the smallest
SkewNode	One node of the skew heap. Contains the value and references to

Module Contents

class data_structures.heap.skew_heap.SkewHeap(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/Skew_heap Visualization: https://www.cs.usfca.edu/~galles/visualization/SkewHeap.html

>>> list(SkewHeap([2, 3, 1, 5, 1, 7]))
[1, 1, 2, 3, 5, 7]

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

>>> sh.insert(1)
>>> sh.insert(-1)
>>> sh.insert(0)
>>> list(sh)
[-1, 0, 1]

__bool__() → bool

Check if the heap is not empty.

>>> sh = SkewHeap()
>>> bool(sh)
False
>>> sh.insert(1)
>>> bool(sh)
True
>>> sh.clear()
>>> bool(sh)
False

__iter__() → collections.abc.Iterator[T]

Returns sorted list containing all the values in the heap.

>>> sh = SkewHeap([3, 1, 3, 7])
>>> list(sh)
[1, 3, 3, 7]

clear() → None

Clear the heap.

>>> sh = SkewHeap([3, 1, 3, 7])
>>> sh.clear()
>>> sh.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.

>>> sh = SkewHeap()
>>> sh.insert(3)
>>> sh.insert(1)
>>> sh.insert(3)
>>> sh.insert(7)
>>> list(sh)
[1, 3, 3, 7]

pop() → T | None

Pop the smallest value from the heap and return it.

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

top() → T

Return the smallest value from the heap.

>>> sh = SkewHeap()
>>> sh.insert(3)
>>> sh.top()
3
>>> sh.insert(1)
>>> sh.top()
1
>>> sh.insert(3)
>>> sh.top()
1
>>> sh.insert(7)
>>> sh.top()
1

_root: SkewNode[T] | None = None

class data_structures.heap.skew_heap.SkewNode(value: T)

Bases: Generic[T]

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

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

Merge 2 nodes together. >>> SkewNode.merge(SkewNode(10),SkewNode(-10.5)).value -10.5 >>> SkewNode.merge(SkewNode(10),SkewNode(10.5)).value 10 >>> SkewNode.merge(SkewNode(10),SkewNode(10)).value 10 >>> SkewNode.merge(SkewNode(-100),SkewNode(-10.5)).value -100

_value: T

left: SkewNode[T] | None = None

right: SkewNode[T] | None = None

property value: T

Return the value of the node.

>>> SkewNode(0).value
0
>>> SkewNode(3.14159).value
3.14159
>>> SkewNode("hello").value
'hello'
>>> SkewNode(None).value

>>> SkewNode(True).value
True
>>> SkewNode([]).value
[]
>>> SkewNode({}).value
{}
>>> SkewNode(set()).value
set()
>>> SkewNode(0.0).value
0.0
>>> SkewNode(-1e-10).value
-1e-10
>>> SkewNode(10).value
10
>>> SkewNode(-10.5).value
-10.5
>>> SkewNode().value
Traceback (most recent call last):
...
TypeError: SkewNode.__init__() missing 1 required positional argument: 'value'

data_structures.heap.skew_heap.T