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

consider each item of the heap as a pair : (the top of the stack (used by the heap to compare), the rest of the stack)

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