<jupyter_start><jupyter_text>Basics Define a heap. Heaps are binary trees for which every parent node has a value less than or equal to any of its children. Load the standard library module that implements heaps. What kind of heaps are supported?<jupyter_code># heapq implements min heaps. Push *-item* to implement max heap.
import heapq<jupyter_output><empty_output><jupyter_text>Turn the below list into a min-heap.<jupyter_code>heap = [1, -4, 7, 50]
heapq.heapify(heap)<jupyter_output><empty_output><jupyter_text>Add *-1* to the heap.<jupyter_code>heapq.heappush(heap, -1)<jupyter_output><empty_output><jupyter_text>Remove and return the smallest element from the heap.<jupyter_code>heapq.heappop(heap)<jupyter_output><empty_output><jupyter_text>Add *-20* to the heap, then remove and return the smalles element.<jupyter_code>heapq.heappushpop(heap, -20)<jupyter_output><empty_output><jupyter_text>Remove and return the smallest element and add *3* to the heap.<jupyter_code>heapq.heapreplace(heap, 3)<jupyter_output><empty_output><jupyter_text>Display the heap.<jupyter_code>heap<jupyter_output><empty_output><jupyter_text>Return the two largest elements on the heap.<jupyter_code>heapq.nlargest(2, heap)<jupyter_output><empty_output><jupyter_text>For the heap below, return the two elements with the smallest digits.<jupyter_code>heap = [("a", 3), ("b", 2), ("c", 1)]
heapq.nsmallest(2, heap, key=lambda x: x[1])<jupyter_output><empty_output><jupyter_text>Applications **Accessing shares** For the shares portfolio below, return the data for the three most expensive shares, sorted in descending order.<jupyter_code>portfolio = [
    {"name": "IBM", "shares": 100, "price": 91.1},
    {"name": "AAPL", "shares": 50, "price": 543.22},
    {"name": "FB", "shares": 200, "price": 21.09},
    {"name": "HPQ", "shares": 35, "price": 31.75},
]
heapq.nlargest(3, portfolio, lambda x: x["price"])<jupyter_output><empty_output><jupyter_text>Do the same using `operator.itemgetter()`.<jupyter_code>from operator import itemgetter

heapq.nlargest(3, portfolio, key=itemgetter("price"))<jupyter_output><empty_output><jupyter_text>Use a faster method that doesn't rely on `heapq` to achieve the same result.<jupyter_code>%timeit sorted(portfolio, key=lambda x: x['price'], reverse=True)[:3]
%timeit heapq.nlargest(3, portfolio, key=lambda x: x['price'])<jupyter_output>2.1 µs ± 6.86 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)<jupyter_text>Calculate the running median for the list below. **Building a priority queue**Use `heapq` to build a priority queue that supports `push()` and `pop()` operations (based on Python Cookbook recipe 1.5 and `heapq` [docs](https://docs.python.org/3/library/heapq.html)). Specifically, build a queue that takes in items of the form `(value, priority)`, returns items in order or priority with higher values signifying higher priority, and breaks priority ties by returning items in the order they were added. To test the list, push the items *(foo, 1)*, *(bar, 3)*, and *(baz, 3)*. The first pop should return *(bar, 3)*.<jupyter_code>import heapq


class Item:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return "Item({!r})".format(self.name)


class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]
q = PriorityQueue()
q.push(Item("foo"), 1)
q.push(Item("bar"), 3)
q.push(Item("baz"), 3)
q.pop()<jupyter_output><empty_output><jupyter_text>**Running median** Write a program that calculates the running median and test it on the list below.<jupyter_code>def running_median(sequence):
    min_heap, max_heap, result = [], [], []
    for x in sequence:
        heapq.heappush(max_heap, -heapq.heappushpop(min_heap, x))
        if len(max_heap) > len(min_heap):
            heapq.heappush(min_heap, -heapq.heappop(max_heap))
        result.append(
            (min_heap[0] + -max_heap[0]) / 2
            if len(min_heap) == len(max_heap)
            else min_heap[0]
        )
    return result
a = [1, 30, 2, -7, 99, 10]

running_median(a)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13446749009554881, 'fraction_numerical': 0.02027499417385225, 'mean_word_length': 5.02808988764045, 'pattern_counts': {'":': 12, '<': 56, '<?xml version=': 0, '>': 57, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '625742', 'license': 'MIT', 'n_tokens_mistral': 1541, 'n_tokens_neox': 1451, 'n_words': 414, 'path': 'content/post/heaps/heaps.ipynb', 'repo_name': 'fabiangunzinger/wowchemy', 'size': '4291'}