Title: Two-pass Pairing Heap with Multipass Auxiliary List
Submitter: Raymond Hettinger (other recipes)
Last Updated: 2004/11/26
Version no: 1.3
Category: Algorithms

Description:

Pairing heap refinement for fewer comparisons.

Source: Text Source

""" Two-pass pairing heap with multipass auxiliary list

This recipe adds a multipass auxiliary list to Tim Peter's code
for a two-pass pairing heap presented at:

    http://mail.python.org/pipermail/python-dev/2002-August/027531.html

The refinement produces a more balanced initial heap when fed with
random data.  This results in fewer comparisons than the basic
two-pass heap.  Details, analysis, and diagrams can be found at:

    http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm

For random data, this implementation still makes more comparisons than
a sort using heapq or the builtin sort.  For partially ordered data, it
can perform better than the builtin sort.  Because of the list of lists
data structure, it always takes more memory than either heapq or the
builtin sort.

"""

from collections import deque

def _link(x, y):
    if x[0] <= y[0]:
        x.append(y)
        return x
    else:
        y.append(x)
        return y

def _merge(x):
    n = len(x)
    if n == 1:
        return []
    pairs = [_link(x[i], x[i+1]) for i in xrange(1, n-1, 2)]
    if n & 1 == 0:
        pairs.append(x[-1])
    pairs.reverse()
    x = pairs.pop()
    for i in pairs:
        x = _link(i, x)
    return x

class AuxList(deque):

    def multipass(self):
        while len(self) > 1:
            self.appendleft(_link(self.pop(), self.pop()))
        return self.pop()

class Heap:

    def __init__(self, iterable=[]):
        self.x = []
        self.aux = AuxList([[value] for value in iterable])

    def __nonzero__(self):
        return bool(self.x)

    def push(self, value):
        self.aux.append([value])

    def pop(self):
        if self.aux:
            self.x += self.aux.multipass()
        result = self.x[0]  # raises IndexError if empty
        self.x = _merge(self.x)
        return result

    def __getitem__(self, i):
        'Hack to make sorting as easy as:  list(Heap(input))'
        return self.pop()    

## Example call
>>> print list(Heap('abracadabra'))
['a', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'd', 'r', 'r']

Discussion:

For versions before Py2.4, subclass from list instead of collections.deque:

class AuxList(list):

    def multipass(self):
        while len(self) > 1:
            self[0:0] = [_link(self.pop(), self.pop())]
        return self.pop()