[Solved] CS300 Homework #4-Binary Heap

In this homework, you will write a program that finds and maintains the median of streaming integers. Your program must store all integers as well as updating the median value as new inputs arrive. To achieve both goals, your program must make use of the Heap data structure in the background. The program will utilize two heaps: a MaxHeap and a MinHeap . Each streamed integer will be stored in the appropriate Heap in O(logN). Using the capabilities of the heap data structure, the program tells the median in O(1) time complexity.

Therefore, you have to provide a Heap implementation which is used as both MaxHeap and MinHeap in the program flow.

Note that this an implementation of Question 11 of Recitation 5.

Program Flow

Streaming integers will be read from .txt files. Each integer at each file will be considered as the next integer in the stream. Therefore you are going to get a name of a file from the console until Ctrl + Z is pressed, which ends the input (HINT: You may use getline(cin, fileName)). After getting the name of each file, you have to open the input file and process all the integers in it. The files will contain only signed integers and you do not have to do input checks. Please check sample runs and sample input files. After processing each file, you have to prompt the current median.

Insertions:

As mentioned before, your program has to run a MaxHeap and a MinHeap. Depending on the current value of median , you will insert the next integer either to the MaxHeap or the MinHeap. Particularly, MaxHeap is responsible for storing the integers less than the median , and MinHeap stores the integers greater than the median. Therefore, new insertions will be made in this fashion. Telling the Median:

If the number of elements in both Heaps are equal, the median is the average of the top elements of the MaxHeap and MinHeap. Otherwise, it is equal to the top element of the one which has more elements. Note that the difference in the number of elements between the heaps is either 1 or 0. Also note that the top element refers to the maximum element for MaxHeap and the minimum element for MinHeap, which can be decided at O(1).

Rules:

• You have to use Heaps, no other data structure or sorting methods are allowed.
• You cant give separate implementations for MaxHeap and MinHeap . Code duplications will lose points. You have to create a class hierarchy and use polymorphism or use function pointers.
• Heap implementation must be template.

Input:

The file names will be received from the console until the input is ended by the user.

Output:

After processing each file, you need to print out the current median.

Sample Run 1:

Please enter the next filename that contains integer stream: input1.txt current median: 520

Please enter the next filename that contains integer stream: input2.txt current median: 487

Please enter the next filename that contains integer stream: input3.txt current median: 481

Please enter the next filename that contains integer stream: input4.txt current median: 434.5

Please enter the next filename that contains integer stream: CtrlZ Press