(original) (raw)

''' Originally written in 2006 Josiah Carlson Released into the public domain. This module implements a "pairing heap" that keeps track of where values are so that adjust_key(value, time) operations can be fast. It has the possibly unfortunate feature that all values must be unique. Running times of pair heap operations: empty() -> O(1) peek() -> O(1) meld(other) -> O(min(n+m, mlog(n+m))) adjust_key(value, time) -> O(logn) delete(value) -> O(logn) extract(n=0) -> O(logn) extract_all() -> O(nlogn) #uses list.sort() because it is faster values() -> O(n) The sequence interface should be ignored by the user, as certain operations (like append) make certain assumptions about later operations that may only be preserved when using the above pair heap operations. ''' import heapq import math #entries in the heap are lists of length 2 class pair(object): if 1: __slots__ = ['time', 'value'] def __init__(self, time, value): self.time = time self.value = value def __cmp__(self, other): return cmp(self.time, other.time) def __repr__(self): return ""%(self.time, self.value) def heapremove(heap, posn): if posn != len(heap) - 1: heap[posn], heap[-1] = heap[-1], heap[posn] toss = heap.pop() heapq._siftdown(heap, 0, posn) heapq._siftup(heap, posn) class pair_heap: if 1: __slots__ = ['h', 'm'] def __init__(self): self.h = [] #list of pairs self.m = {} # key:posn mapping def empty(self): return not len(self) def peek(self): return self.h[0].value def meld(self, other): ls = len(self) lo = len(other) if ls + lo <= lo*math.log(max(ls+lo, math.e)): for i in other.h: self.append(i) other.h, other.m = [], {} #required by the above .append() calls due to collisions heapq.heapify(self) else: #insert/adjust the keys one by one for i in other.h: self.adjust_key(i.value, i.time) other.h, other.m = [], {} def adjust_key(self, value, time): if value not in self.m: heapq.heappush(self, pair(time, value)) return posn = self.m[value] self.h[posn].time = time heapq._siftdown(self, 0, posn) heapq._siftup(self, posn) def delete(self, value): if value not in self.m: return heapremove(self, self.m[value]) def extract(self, n=0): if n <= 0: return heapq.heappop(self).value return [heapq.heappop(self).value for i in xrange(min(n, len(self)))] def extract_all(self): r, self.h, self.m = self.h, [], {} #faster than performing the heapq heappop repeatedly r.sort() return [i.value for i in r] def values(self): return [i.value for i in self.h] # required for heapq which assumes the sequence interface. def __len__(self): return len(self.h) def __setitem__(self, posn, p): oldvalue = self.h[posn] self.h[posn] = p if self.m[oldvalue.value] == posn: del self.m[oldvalue.value] self.m[p.value] = posn def __getitem__(self, posn): return self.h[posn] def __delitem__(self, posn): self.pop(posn) def __contains__(self, value): return value in self.m def pop(self, posn=-1): lsh = len(self.h) if posn < 0: posn += lsh if posn != lsh-1: raise IndexError("pair index out of range") a = self.h.pop() del self.m[a.value] return a def append(self, p): if p.value in self.m: #item already in heap, may be an error? #also may want to update due to meld? #will keep smallest and assume that heapify will occur po = self.m[p.value] if self.h[po].time > p.time: self.h[po].time = p.time return self.m[p.value] = len(self.h) self.h.append(p) def __repr__(self): return repr(self.h) def test(): import random for p in xrange(2): ph = pair_heap() for i,j in zip(range(10), [chr(ord('M')-i) for i in xrange(10)]): ph.adjust_key(j, i) random.shuffle(ph) heapq.heapify(ph) ph.adjust_key('Q', 2.5) ph.adjust_key('M', 3.5) ph.delete('G') if p == 0: while len(ph): print heapq.heappop(ph) else: print ph.extract_all() a = pair_heap() b = pair_heap() for i in xrange(10): a.adjust_key('%i_a'%i, i) b.adjust_key('%i_b'%i, i+.5) a.meld(b) print a.extract_all() print b.extract_all() if __name__ == '__main__': test()