TD04 - Stacks and heaps

Implementation in Python 3 of the algorithm merging a heap of stacks seen in exercise 2 of TD 4.

Each function you need to complete is followed by tests to verify that the data produced when the function was called is correct.

We will use a Python module heapq (for heaps (integrated to Python, no need to install). After exploring the documentation, you can play with the following code:

from heapq import *

tas = [(1,'a'), (2,'b')]            
heapify(tas)                        ### creates a min heap from a list in O(n)
heappush(tas, (0,'c'))               ### insertion in O(log n) 
print(heappop(tas))                 ### extraction of (0, 'c') in O(log n)
print(heappop(tas)[0])              ### extraction >>> '1'
print(len(tas))                     ### measure in O(1) >>> 1 
print(heappop(tas)[1])              ### extraction >>> 'b'

In the following cell, we generate a random input to this exercise. It returns a list made of N stacks of integers that represents the N professors' copies. Each stack (one professor copies) is of a random size smaller than M and it is sorted from the lower value (on the top) to the greater (in the bottom). The integers corresponds to the copies grades.

A stack is simply implemented by a Python list where the top of the stack corresponds to the last element of the list.

from random import randint

# N professor, up to M copies each
def random_collection(N, M):
    tab = []

    # for the N professors
    for i in range(N):
        # each professor has a sorted stack of M copies where
        # grades are going from 0 to 100
        copies_group = sorted([randint(0,100) for i in range(randint(1,M))], reverse = True)
        tab.append(copies_group)

    return tab

# 10 professors, up to 20 copies each
copies = random_collection(10, 20)

Complete the create_heap(collection) function that takes as parameter the previously produced collection (list of stacks) and returns the corresponding heap of stacks.

from heapq import *

# we put the copies in a min-heap
def create_heap(collection):
    copies_heap = []

    ############### TODO : complete code #####################    

    return copies_heap

# we will duplicate copies to preserve the original collection
from copy import deepcopy
copies_heap = create_heap(deepcopy(copies))

Complete the following code to obtain from the previously produced heap a unique list that contains all the copies and that is still sorted.

# the unique list of copies
copies_flat = []

while len(copies_heap) > 0:

    ############### TODO : complete code #####################    


# testing against a brute sort of the original collection
assert copies_flat == sorted([copy for stack in copies for copy in stack])