usrbinenv python3 one node of the randomized heap contains the value and references to two children return the value of the node rhn randomizedheapnode10 rhn value 10 rhn randomizedheapnode10 rhn value 10 merge 2 nodes together rhn1 randomizedheapnode10 rhn2 randomizedheapnode20 randomizedheapnode mergerhn1 rhn2 value 10 rhn1 randomizedheapnode20 rhn2 randomizedheapnode10 randomizedheapnode mergerhn1 rhn2 value 10 rhn1 randomizedheapnode5 rhn2 randomizedheapnode0 randomizedheapnode mergerhn1 rhn2 value 0 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 orgwikirandomizedmeldableheap randomizedheap2 3 1 5 1 7 tosortedlist 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 insert1 rh insert1 rh insert0 rh tosortedlist 1 0 1 rh randomizedheap3 1 3 7 rh tosortedlist 1 3 3 7 insert the value into the heap rh randomizedheap rh insert3 rh insert1 rh insert3 rh insert7 rh tosortedlist 1 3 3 7 pop the smallest value from the heap and return it rh randomizedheap3 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 return the smallest value from the heap rh randomizedheap rh insert3 rh top 3 rh insert1 rh top 1 rh insert3 rh top 1 rh insert7 rh top 1 clear the heap rh randomizedheap3 1 3 7 rh clear rh pop traceback most recent call last indexerror can t get top element for the empty heap returns sorted list containing all the values in the heap rh randomizedheap3 1 3 7 rh tosortedlist 1 3 3 7 check if the heap is not empty rh randomizedheap boolrh false rh insert1 boolrh true rh clear boolrh false usr bin env python3 one node of the randomized heap contains the value and references to two children return the value of the node rhn randomizedheapnode 10 rhn value 10 rhn randomizedheapnode 10 rhn value 10 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 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 rh randomizedheap 3 1 3 7 rh to_sorted_list 1 3 3 7 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 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 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 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 returns sorted list containing all the values in the heap rh randomizedheap 3 1 3 7 rh to_sorted_list 1 3 3 7 check if the heap is not empty rh randomizedheap bool rh false rh insert 1 bool rh true rh clear bool rh false
from __future__ import annotations

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

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


class RandomizedHeapNode(Generic[T]):
    

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

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

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

        if not root2:
            return root1

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

        if random.choice([True, False]):
            root1.left, root1.right = root1.right, root1.left

        root1.left = RandomizedHeapNode.merge(root1.left, root2)

        return root1


class RandomizedHeap(Generic[T]):
    

    def __init__(self, data: Iterable[T] | None = ()) -> None:
        
        self._root: RandomizedHeapNode[T] | None = None

        if data:
            for item in data:
                self.insert(item)

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

    def pop(self) -> T | None:
        

        result = self.top()

        if self._root is None:
            return None

        self._root = RandomizedHeapNode.merge(self._root.left, self._root.right)

        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

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

        return result

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


if __name__ == "__main__":
    import doctest

    doctest.testmod()