Homework 3
Examine the behaviour of these two data structures on test data generated by the program described below. The test data contains sets of varying sizes with three kinds of operations:
random test: a sequence in which the number of insert, decrease_key, and delete_min operations are approximately equally distributed;
biased test: a sequence in which there are considerable fewer delete_min operations than in the random test;
special test: a sequence to be tested against the naive implementation of the Fibonacci heap.
Your task is to determine the average number of steps that a delete_min operation takes. The number of steps of one such operation is the number of children of the deleted node that are appended to the list of trees, plus the number of times some tree is linked to another tree during the subsequent consolidation procedure.
Generating the data
Download the generator and run it with the following parameters:
-s XX, where XX are the last two digits of your student ID;
-r, to generate the random test;
-b, to generate the biased test;
-x, to generate the special test.
The output of the generator is a text file. Each line specifies a single operation on the tree:
# N: start a test in which N elements need to be stored in a heap – discard the previous heap and create a new one (the set size can be useful for plotting);
INS E K: insert the element E with key K to the heap;
DEL: delete the element with minimum key (if several elements have the same key, only delete one of them);
DEC E K: decrease the key of element E to key K (if the element E does not exist, or its key is smaller than K already, ignore this operation).
A single call of the generator creates a sequence of tests with at most 2.000.000 elements each. The element identifiers E are integers from 0 to N-1. Each identifier is unique, i.e. you can assume that at any time there is at most one element with identifier E stored in the heap. However after an element was deleted it may be inserted again at a later time. The keys K are not unique, i.e. at any time there may be several elements with the same key stored in the heap. Make sure you have pointers to elements so you have direct access to them during a decrease_key operation.
Resulting graphs
Draw plots showing the dependence of the average number of steps of a delete_min operation on the size N. The number of steps of one such operation is the number of children of the deleted node that are appended to the list of trees, plus the number of times some tree is linked to another tree during the subsequent consolidation procedure.
A graph showing two plots of the average number of steps of a delete_min operation in the proper Fibonacci heap (not the naive version): one plot for the random test and one for the biased test. How do you explain the difference between the plots of the two tests?
For the special test, a graph showing two plots of the average number of steps of a delete_min operation: one for the proper Fibonacci heap and one for the naive version. Can you tell what approximately the asymptotic growth rate of each plot is?
Example input
# 4 INS 0 3 DEC 0 0 DEL INS 1 2 DEC 1 0 DEL INS 2 1 DEC 2 0 INS 3 3 # 5 INS 0 3 DEL DEC 0 0 INS 1 1 DEC 1 0 DEL INS 2 4 INS 3 4 DEC 3 0 DEC 2 0 DEL DEL INS 2 2