Create a class and call it MaxPriorityQueue which represents a max heap. You only need to change < to > in method add. You will use both class SortedPriorityQueue and MaxPriorityQeueue to solve the problem of finding the median value of a stream of integers. Median is the middle value of an ordered data set. For a set of integers, there are just as many elements less than the median as greater. In an ordered set of: odd number of integers, the middle element is the median – in the ordered set { 5, 7, 8, 10, 15 }, the median is 8 even number of integers, there's no middle element; the median is computed as the average of the two middle elements – in the ordered set {5, 7, 8, 10}, the median is (7 + 8) / 2 = 7.5 Assume that instead of a finite set, we're reading integers off a data stream. We can define the median of a stream of integers as the median of the set of integers read so far. To solve the problem, we can use two heaps, one holds the lower half and another for the upper half, and keep them balanced, they only differ in size by 1. Max heap: keeps numbers of the lower half, so the root of the heap is the max value Min heap: keeps the numbers of the upper half, the root of the heap is the min value With these two heaps, we can compute the effective (current) median, by only reading the root(s), which is a O(1) operation. But the solution complexity is O(nlogn). Here is an algorithm that describes the solution, your task is to implement the algorithm. Emulate the stream of numbers by randomly generated values of your choice, when each number is generated, you need to compute the median of the numbers generated so far. The Python Algorithm Create two heaps. One max heap (maxheap) to maintain elements of the lower half and one min heap(minheap) to maintain elements of the higher half at any point in time. Initially, the value of median is 0. For the current element received from the stream insert it into either of the heaps and calculate the median described in the following statements. If the size of both the heaps is the same. if the current element is greater than the median value, insert it into min heap, return the root of minheap as the new median. else if the current element is less than the median value, insert it into max heap, return the root of maxheap as the new median. else If the size of maxheap is greater than minheap : if the current element is greater than the median, insert the current element in minheap. else if the current element is less than the median, pop the root of maxheap and insert it into minheap. Now insert the current element to maxheap. calculate the median as an average of the root of minheap and maxheap. else If the size of maxheap is less than minheap : if the current element is less than the median, insert the current element into maxheap. else if the current element is greater than the median, pop the top of minheap and insert it into maxheap. Now insert the current element to minheap. calculate the median as an average of the root of minheap and maxheap.

Create a class and call it MaxPriorityQueue which represents a max heap. You only need to change < to > in method add. You will use both class SortedPriorityQueue and MaxPriorityQeueue to solve the problem of finding the median value of a stream of integers. Median is the middle value of an ordered data set. For a set of integers, there are just as many elements less than the median as greater. In an ordered set of: odd number of integers, the middle element is the median – in the ordered set { 5, 7, 8, 10, 15 }, the median is 8 even number of integers, there's no middle element; the median is computed as the average of the two middle elements – in the ordered set {5, 7, 8, 10}, the median is (7 + 8) / 2 = 7.5 Assume that instead of a finite set, we're reading integers off a data stream. We can define the median of a stream of integers as the median of the set of integers read so far. To solve the problem, we can use two heaps, one holds the lower half and another for the upper half, and keep them balanced, they only differ in size by 1. Max heap: keeps numbers of the lower half, so the root of the heap is the max value Min heap: keeps the numbers of the upper half, the root of the heap is the min value With these two heaps, we can compute the effective (current) median, by only reading the root(s), which is a O(1) operation. But the solution complexity is O(nlogn). Here is an algorithm that describes the solution, your task is to implement the algorithm. Emulate the stream of numbers by randomly generated values of your choice, when each number is generated, you need to compute the median of the numbers generated so far. The Python Algorithm Create two heaps. One max heap (maxheap) to maintain elements of the lower half and one min heap(minheap) to maintain elements of the higher half at any point in time. Initially, the value of median is 0. For the current element received from the stream insert it into either of the heaps and calculate the median described in the following statements. If the size of both the heaps is the same. if the current element is greater than the median value, insert it into min heap, return the root of minheap as the new median. else if the current element is less than the median value, insert it into max heap, return the root of maxheap as the new median. else If the size of maxheap is greater than minheap : if the current element is greater than the median, insert the current element in minheap. else if the current element is less than the median, pop the root of maxheap and insert it into minheap. Now insert the current element to maxheap. calculate the median as an average of the root of minheap and maxheap. else If the size of maxheap is less than minheap : if the current element is less than the median, insert the current element into maxheap. else if the current element is greater than the median, pop the top of minheap and insert it into maxheap. Now insert the current element to minheap. calculate the median as an average of the root of minheap and maxheap.

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

INFO

Create a class and call it MaxPriorityQueue which represents a max heap. You only need to change < to > in method add.

You will use both class SortedPriorityQueue and MaxPriorityQeueue to solve the problem of finding the median value of a stream of integers.

Median is the middle value of an ordered data set. For a set of integers, there are just as many elements less than the median as greater. In an ordered set of:

odd number of integers, the middle element is the median – in the ordered set { 5, 7, 8, 10, 15 }, the median is 8
even number of integers, there's no middle element; the median is computed as the average of the two middle elements – in the ordered set {5, 7, 8, 10}, the median is (7 + 8) / 2 = 7.5

Assume that instead of a finite set, we're reading integers off a data stream. We can define the median of a stream of integers as the median of the set of integers read so far.

To solve the problem, we can use two heaps, one holds the lower half and another for the upper half, and keep them balanced, they only differ in size by 1.

Max heap: keeps numbers of the lower half, so the root of the heap is the max value
Min heap: keeps the numbers of the upper half, the root of the heap is the min value

With these two heaps, we can compute the effective (current) median, by only reading the root(s), which is a O(1) operation. But the solution complexity is O(nlogn).

Here is an algorithm that describes the solution, your task is to implement the algorithm. Emulate the stream of numbers by randomly generated values of your choice, when each number is generated, you need to compute the median of the numbers generated so far.

The Python Algorithm

Create two heaps. One max heap (maxheap) to maintain elements of the lower half and one min heap(minheap) to maintain elements of the higher half at any point in time.
Initially, the value of median is 0.
For the current element received from the stream insert it into either of the heaps and calculate the median described in the following statements.
If the size of both the heaps is the same.
- if the current element is greater than the median value, insert it into min heap, return the root of minheap as the new median.
- else if the current element is less than the median value, insert it into max heap, return the root of maxheap as the new median.
else If the size of maxheap is greater than minheap :
- if the current element is greater than the median, insert the current element in minheap.
- else if the current element is less than the median, pop the root of maxheap and insert it into minheap. Now insert the current element to maxheap.
- calculate the median as an average of the root of minheap and maxheap.
else If the size of maxheap is less than minheap :
- if the current element is less than the median, insert the current element into maxheap.
- else if the current element is greater than the median, pop the top of minheap and insert it into maxheap. Now insert the current element to minheap.
- calculate the median as an average of the root of minheap and maxheap.