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?

Turn the below list into a min-heap.

Add -1 to the heap.

Remove and return the smallest element from the heap.

Add -20 to the heap, then remove and return the smalles element.

Remove and return the smallest element and add 3 to the heap.

Display the heap.

Return the two largest elements on the heap.

For the heap below, return the two elements with the smallest digits.

Applications

Accessing shares

For the shares portfolio below, return the data for the three most expensive shares, sorted in descending order.

Do the same using operator.itemgetter().

Use a faster method that doesn't rely on heapq to achieve the same result.

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

Running median

Write a program that calculates the running median and test it on the list below.

Sources