Welcome, guest | Sign In | My Account | Store | Cart

Pairing heap refinement for fewer comparisons.

Python, 77 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
""" 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']

For versions before Py2.4, subclass from list instead of collections.deque: <pre> class AuxList(list):

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

</pre>

1 comment

Christos Georgiou 17 years, 10 months ago  # | flag

[0:0] vs .insert(0, Any special reason to prefer lst[0:0]= [obj] over lst.insert(0, obj)? I am asking out of curiosity.

Created by Raymond Hettinger on Sat, 10 Apr 2004 (PSF)
Python recipes (4591)
Raymond Hettinger's recipes (97)

Required Modules

  • (none specified)

Other Information and Tasks