Heap drills
Drills for working with Heaps in Python.
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 minheap.




Add 1 to the heap.


Remove and return the smallest element from the heap.


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


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


1
Display the heap.


[1, 3, 7, 50]
Return the two largest elements on the heap.


[50, 7]
For the heap below, return the two elements with the smallest digits.




[('c', 1), ('b', 2)]
Applications
Accessing shares
For the shares portfolio below, return the data for the three most expensive shares, sorted in descending order.




[{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'HPQ', 'shares': 35, 'price': 31.75}]
Do the same using operator.itemgetter()
.


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


588 ns ± 16.9 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)


2.1 µs ± 6.86 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
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).




Item('bar')
Running median
Write a program that calculates the running median and test it on the list below.




[1, 15.5, 2, 1.5, 2, 6.0]