Assignment 4: Heap

Due: Oct 4, 11.55PM

(Submit at moodle.)

In this assignment you are given a binary tree on n nodes with the structural property of a heap i.e. if 2h-1 <= n < 2h+1 -1 then the top h levels of the tree are complete and the last level has n - (2h-1) nodes in the first positions from the left. But, unfortunately, the priorities in these nodes do not necessarily satisfy the heap order property i.e. there may be some nodes whose priority is greater than the priority of one or both of its children.

You have to write a program to restore heap order to this heap i.e. make a heap out of it.

Implementation Notes:

Input format:

The input will be taken from file. The file will contain as many lines as there are non-empty levels in the heap. Each line will contain the priority values listed from left to right separated by spaces.

For example, the following input

5
3 8
12 17 14 2
6

represents a heap that has 5 at the root. The root's two children contain the priorities 3 (left child) and 8 (right child). The node containing 3 has the priority 12 in its left child and 17 in its right child etc. The fourth level has only one node which is the left child of the node containing the priority 12 and that node contains the priority value 6. Your output should be given in the same format as the input.

You are not allowed to take the numbers one at a time and then insert them incrementally into a heap. You have to create the structure as given in the input file and then correct the heap order only through swaps/bubbling operations.

Notes: