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:
return self.pop()
``````

</pre>

#### 1 comment

Christos Georgiou 17 years, 11 months ago

[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)

### Required Modules

• (none specified)