usrbinenv python3 one node of the skew heap contains the value and references to two children return the value of the node return self value staticmethod def merge root1 skewnodet none root2 skewnodet none skewnodet none a data structure that allows inserting a new value and to pop the smallest values both operations take ologn time where n is the size of the structure wiki https en wikipedia orgwikiskewheap visualization https www cs usfca edugallesvisualizationskewheap html listskewheap2 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 insert1 sh insert1 sh insert0 listsh 1 0 1 sh skewheap3 1 3 7 listsh 1 3 3 7 check if the heap is not empty sh skewheap boolsh false sh insert1 boolsh true sh clear boolsh false returns sorted list containing all the values in the heap sh skewheap3 1 3 7 listsh 1 3 3 7 pushing items back to the heap not to clear it insert the value into the heap sh skewheap sh insert3 sh insert1 sh insert3 sh insert7 listsh 1 3 3 7 pop the smallest value from the heap and return it sh skewheap3 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 return the smallest value from the heap sh skewheap sh insert3 sh top 3 sh insert1 sh top 1 sh insert3 sh top 1 sh insert7 sh top 1 clear the heap sh skewheap3 1 3 7 sh clear sh pop traceback most recent call last indexerror can t get top element for the empty heap usr bin env python3 one node of the skew heap contains the value and references to two children return the value of the node merge 2 nodes together 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 sh skewheap 3 1 3 7 list sh 1 3 3 7 check if the heap is not empty sh skewheap bool sh false sh insert 1 bool sh true sh clear bool sh false returns sorted list containing all the values in the heap sh skewheap 3 1 3 7 list sh 1 3 3 7 pushing items back to the heap not to clear it 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 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 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 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
from __future__ import annotations

from collections.abc import Iterable, Iterator
from typing import Any, Generic, TypeVar

T = TypeVar("T", bound=bool)


class SkewNode(Generic[T]):
    

    def __init__(self, value: T) -> None:
        self._value: T = value
        self.left: SkewNode[T] | None = None
        self.right: SkewNode[T] | None = None

    @property
    def value(self) -> T:
        
        return self._value

    @staticmethod
    def merge(
        root1: SkewNode[T] | None, root2: SkewNode[T] | None
    ) -> SkewNode[T] | None:
        
        if not root1:
            return root2

        if not root2:
            return root1

        if root1.value > root2.value:
            root1, root2 = root2, root1

        result = root1
        temp = root1.right
        result.right = root1.left
        result.left = SkewNode.merge(temp, root2)

        return result


class SkewHeap(Generic[T]):
    

    def __init__(self, data: Iterable[T] | None = ()) -> None:
        
        self._root: SkewNode[T] | None = None
        if data:
            for item in data:
                self.insert(item)

    def __bool__(self) -> bool:
        
        return self._root is not None

    def __iter__(self) -> Iterator[T]:
        
        result: list[Any] = []
        while self:
            result.append(self.pop())

        
        for item in result:
            self.insert(item)

        return iter(result)

    def insert(self, value: T) -> None:
        
        self._root = SkewNode.merge(self._root, SkewNode(value))

    def pop(self) -> T | None:
        
        result = self.top()
        self._root = (
            SkewNode.merge(self._root.left, self._root.right) if self._root else None
        )

        return result

    def top(self) -> T:
        
        if not self._root:
            raise IndexError("Can't get top element for the empty heap.")
        return self._root.value

    def clear(self) -> None:
        
        self._root = None


if __name__ == "__main__":
    import doctest

    doctest.testmod()