Looking For An Inverted Heap In Python

I'd like to comb off the n largest extremes from a timeseries. heapq works perfectly for the nlargest def nlargest(series, n): count = 0 heap = [] for e in series:

Solution 1:

You can easily 'create' an inverted heap by multiplying the priorities of your items by -1.

So your nsmallest simply needs to be told how to 'invert' the priorities, decorating each value as needed:

defnsmallest(series, n, invert=lambda x: -1 * x):
    count = 0
    heap = []
    for e in series:
        if count < n:
            count += 1
            hp.heappush(heap, (invert(e), e))
        else:
            # keeps heap size fixed
            hp.heappushpop(heap, (invert(e), e))  
    # note: heap[0][1] is largest, remove inverted prioritiesreturn [h[1] for h in heap]

Note that we use a (invertedpriority, value) tuple to keep the heap inverted.

For non-numericals, you'd have to simply provide a inversion function that turns the priorities upside down, it only needs to be a simple key, not something that is readable or anything:

alphanumeric_invert = lambda x: [(ord(c) * -1) for c in x] 

However, rather than write your own, you want to use the heapq.nsmallest() function, which uses an optimised max-heap implementation (there is an internal _heappop_max() function it uses), which also adds a tie-breaker counting value to keep the sort stable. And there is a matching heapq.nlargest() function.

Solution 2:

Use heapq.nsmallest from the Python standard library:

heapq.nsmallest(n, iterable[, key])

Return a list with the n smallest elements from the dataset defined by iterable. Equivalent to: sorted(iterable, key=key)[:n]