Pairing heap refinement for fewer comparisons.
Python, 77 lines
Download
Copy to clipboard1 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>
Tags: algorithms
[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.