Python 3 pairing heap implementation with decrease-key

pairheap.py

# Pairing heap implementation with decrease-key functionality

class Wrapper:
    """
    A wrapper for maintaining a reference to the root of the heap
    """
    def __init__(self):
        self._root = Heap()

    def __len__(self):
        return len(self._root)

    def min(self):
        return self._root

    def insert(self, val, props={}):
        self._root, sub = self._root.insert(val, props)
        return sub

    def add(self, val, props={}):
        "Chainable version of insert. Doesn't return subheap reference"
        self._root, _ = self._root.insert(val, props)
        return self

    def delete_min(self):
        self._root = self._root.delete_min()

    def pop(self):
        val, props, self._root = self._root.pop()
        return ( val, props )

    def decrease_key(self, node, val):
        self._root = node.decrease_key(val)

    @classmethod
    def from_list(cls, list):
        q = cls()
        for val in list:
            if type(val) is tuple:
                q.insert(val[0], val[1])
            else:
                q.insert(val)
        return q

    def to_list(self):
        "Perform a non-destructive heapsort"

        # Deep copy of values
        q = Wrapper()
        for val, _ in self._root:
            q.insert(val)

        # Heap sort
        sorted = []
        while True:
            val, _ = q.pop()
            if val is None:
                return sorted
            sorted.append(val)

class Heap:
    """
    A heap is merely a collection of subheaps associated with a value with a well-
    defined order, so there is no distinction between a heap and its nodes.
    """
    def __init__(self, val=None, props={}):
        self.val = val
        self.props = props

        self._size = 0 if val is None else 1
        self._heaps = None # An empty singly-linked list
        self._parent = None

    def __len__(self):
        return self._size

    def __iter__(self):
        if self.val is not None:
            yield ( self.val, self.props )
            if self._heaps is not None:
                for h in LinkedList(self._heaps):
                    for v in h:
                        yield v

    def insert(self, val, props={}):
        h = Heap(val, props)
        return ( Heap._meld(self, h), h )

    def delete_min(self):
        def mapper(x):
            x._parent = self._parent
            return x
        self._heaps = LinkedList.map(self._heaps, mapper)
        return Heap._pair(self._heaps)

    def pop(self):
        return ( self.val, self.props, self.delete_min() )

    def _find_root(self):
        if self._parent is None:
            return self
        return self._parent._find_root()

    def _orphan(self, child):
        self._heaps = LinkedList.filter(self._heaps, lambda x: x is not child)
    
    def decrease_key(self, val):
        self.val = val

        root = self._find_root()
        if self is root:
            return self
        else:
            self._parent._orphan(self)
            self._parent = None
            return Heap._meld(self, root)

    @staticmethod
    def _meld(Q1, Q2):
        if Q1.val is None and Q2.val is None:
            raise Exception("Cannot merge two empty heaps")
        elif Q1.val is None:
            return Q2
        elif Q2.val is None:
            return Q1
        elif Q1.val < Q2.val:
            Q1._size += Q2._size
            Q1._heaps = (Q2, Q1._heaps)
            Q2._parent = Q1
            return Q1
        else:
            Q2._size += Q1._size
            Q2._heaps = (Q1, Q2._heaps)
            Q1._parent = Q2
            return Q2
    
    @staticmethod
    def _pair(qs):
        if qs is None:
            return Heap()
        elif qs[1] is None:
            return qs[0]
        else:
            return Heap._meld(Heap._meld(qs[0], qs[1][0]), Heap._pair(qs[1][1]))

class LinkedList:
    """
    Utility class for operating on constructed linked lists from tuples
    """
    def __init__(self, list):
        self.list = list

    def __iter__(self):
        list = self.list
        while list is not None:
            yield list[0]
            list = list[1]

    @staticmethod
    def map(lst, f):
        mapped = None
        while lst is not None:
            mapped = ( f(lst[0]), mapped )
            lst = lst[1]
        return mapped # order doesn't matter, so no need to reverse

    @staticmethod
    def filter(lst, f):
        filtered = None
        while lst is not None:
            if f(lst[0]):
                filtered = ( lst[0], filtered )
            lst = lst[1]
        return filtered # order doesn't matter, so no need to reverse

def _main():
    root = Wrapper()
    root.add(1).add(4).add(3)
    print(root.to_list())

    root = Wrapper.from_list([1,4,7,3,6,2,3,5,9])
    print(root.to_list())

if __name__ == '__main__':
    _main()