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.

PrlorityQueueBase.py
class PriorityQueueBase:
*"Abstract base class for a priority queue.""
nested _Item class
class _Item:
an"Lightweight composite to store priority queue items.""
-_slots_ ='_key','_value'
def _init_(self, k, v):
self._key = k
self._value = v
defIt_(self, other):
return self._key < other._key # compare items based on their keys
def _repr__(self):
--
return '{0),(1})!format(self._key, self._value)
public behaviors
# concrete method assuming abstract len
#3-
def is_empty(self):
an"Return True if the priority queue is empty.""
return len(self) == 0
def _len_(self):
an"Return the number of items in the priority queue."
raise NotimplementedError('must be implemented by subclass')
def add(self, key, value):
"Add a key-value pair.""
raise NotimplementedError('must be implemented by subclass')
def min(self):
an"Return but do not remove (k,v) tuple with minimum key.
Raise Empty exception if empty.
ann
raise NotimplementedError('must be implemented by subclass')
def remove_min(self):
"Remove and return (k,v) tuple with minimum key.
Raise Empty exception if empty.
ann
raise NotimplementedError('must be implemented by subclass')

SortedPrlorityQueue.py -
from priorityqueue.PriorityQueueBase import PriorityQueueBase
from linkedlists import Positional List
import priorityqueue.Empty
class SortedPriorityQueue(PriorityQueueBase): # base class defines _Item
**"A min-oriented priority queue implemented with a sorted list.*
#-
def _init_(self):
an"Create a new empty Priority Queue."
self._data = PositionalList)
public behaviors
def _len__(self):
an"Return the number of items in the priority queue."
return len(self._data)
def add(self, key, value):
"Add a key-value pair.""
newest = self._Item(key, value)
walk = self._data.last()
while walk is not None and newest < walk.element():
# make new item instance
# walk backward looking for smaller key
walk = self._data.before(walk)
if walk is None:
self._data.add_first(newest)
else:
# new key is smallest
self._data.add_after(walk, newest)
# newest goes after walk
def min(self):
an"Return but do not remove (k,v) tuple with minimum key.
Raise Empty exception if empty.
ann
if self.is_empty():
raise Empty('Priority queue is empty:)
p = self._data.first)
item = p.element()
return (item._key, item._value)
def remove_min(self):
an"Remove and return (k,v) tuple with minimum key.
Raise Empty exception if empty.
ann
if self.is_empty():
raise Empty('Priority queue is empty:)
item = self._data.delete(self._data.first()
return (item._key, item._value)

Expert Solution

Step by step

Solved in 4 steps with 3 images

SEE SOLUTION Check out a sample Q&A here