Solve this problem using LinkedList. Solution to the problem is posted below using HEAP. Following the same format of the solution, provide a solution using LinkedList

Proof of correctness:

Formally, the proof can be conducted via a loop invariant. The main argument is that

during the execution of the algorithm all written elements are smaller than the current

heap elements as well as all future stream elements.

Initialization: Prior to the execution of Min-Insert-Heapify(), there is no element written

to the output file.

Maintenance: At the time an element x is written, it is the smallest among all 101 heap

elements e1,,e101. Therefore, at this time 100 elements larger than x have been

observed. If at any future time an element y with an even smaller time-stamp than x

would be observed, y would be distorted by at least 101 positions (the heap elements e1,

,e101) in contradiction to the assumption that no stream element can be more than 100

positions out of order. Therefore, x is smaller than all other heap elements and any future

stream element, and can be written without violating the loop invariant. Maintenance of

the loop invariant implicates that all elements are written in correct order.

Termination: At termination, all the elements are written into the output file with the

correct sorted order.

Example:

As 100 elements is a bigger number, Let us do it with 2.

Let us start with 3,2,1,4,7

Order of Elements Heap Output

3,2,1,4,7

2,1,4,7

1,4,7

4,7 1,2,3 1

7 2,3,4 1,2

3,4,7 1,2,3,4,7

Time Complexity:

First, call Build-Min-Heap() on the first 101 elements. This has no effect on asymptotic

performance, since it only takes O(1) time. For the remaining stream elements each MinInsert-Heapify() step takes O(1) time since the heap does not increase in size. Therefore,

if n is the number of processed stream elements, our algorithm has an O(n) asymptotic

worst case complexity

Consider a situation where your data is almost sorted-for example you are receiving time-stamped stock quotes and earlier quotes may arrive after later quotes because of differences in server loads and network traffic routes. Focus only on the time-stamps. To simplify this problem, assume that each time-stamp is an integer, all time-stamps are different, and for any two time-stamps, the earlier time-stamp corresponds to a smaller integer than the later time-stamp. The time-stamps arrive in a stream that is too large to be kept in memory completely. The time-stamps in the stream are not in their correct order, but you know that every time-stamp (integer) in the stream is at most hundred positions away from its correctly sorted position. Design an algorithm that outputs the time-stamps in the correct order. You can only a constant amount of storage, i.e., the memory used should be independent of the number of time-stamps processed. As a second requirement: your algorithm should use a linked list and NOT a heap