Data Structures 1 - NTIN066 - WS 2014/2015

HW 3

Due date: 15. 12. 2014

Problem description

Implement lazy binomial heaps. Create a program which reads the test data from the standard input and with each Delete-Min operation it outputs the deleted minimum. The input data are partitioned into runs. Each run constists of a sequence of Insert and Delete-Min operations. The Insert operation starts by the character 'I' in the input. The Delete-Min operation starts with 'D'. The last row of the run is the character 'R'. After each run (at the end of the input) there is a row with the character 'X'. The inserted elements are from the interval [0, n - 1]. After each run the binomial heap is emptied. Each run should be saparated by a newline in the output.

Using unix executable /afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl3-gen-data which is available in Rotunda laboratory you can generate test data. Test your implementation using those data and for each run measure the overall number of merges during Delete-Min operation. Then measure the count N of Insert operations and the number D of Delete-Min operations. Create a graph (each run is a point):

That is create a graph of the average number of merges per deletion. The graph should have five curves for five test data. Also try to explain the graph.

Input example

I 1 
I 3
D
I 2
D
I 0
R
I 2
I 3
I 0
I 1
D
R
X

Output

1
2

0

A possible graph

Generating the input data

$/afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl3-gen-data XX D

This will generate data for measuring, remember that XX are the last two number of your student number and D is one of {0,1000,10000,100000,1000000} (the five curves). If D=0, then we perform Delete-Min just after all insertions until the heap is emptied. When D<0, then Delete-Min operations are uniformly positioned among N Insert operations. Each run has at least 1 000 inserts and runs up to 1 000 000 insertions. There are approximately 300 runs. Example: 

pbl3-gen-data 72 0       | my-heap
pbl3-gen-data 72 1000    | my-heap
pbl3-gen-data 72 10000   | my-heap
pbl3-gen-data 72 100000  | my-heap
pbl3-gen-data 72 1000000 | my-heap