Python Exercise: Compute the median of all elements
Python heap queue algorithm: Exercise-16 with Solution
Write a Python program which add integer numbers from the data stream to a heapq and compute the median of all elements. Use Heap queue algorithm.
From Wikipedia "In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population or a probability distribution. For a data set, it may be thought of as the "middle" value. For example, in the data set [1, 3, 3, 6, 7, 8, 9], the median is 6, the fourth largest, and also the fourth smallest, number in the sample. For a continuous probability distribution, the median is the value such that a number is equally likely to fall above or below it."
Sample Solution:
Python Code:
import heapq
class Median_Finder:
def __init__(self):
#initialize data structure
self.max_heap = []
self.min_heap = []
def add_Number(self, num):
#type num: int, rtype: void
if not self.max_heap and not self.min_heap:
heapq.heappush(self.min_heap, num)
return
if not self.max_heap:
if num > self.min_heap[0]:
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
heapq.heappush(self.min_heap, num)
else:
heapq.heappush(self.max_heap, -num)
return
if len(self.max_heap) == len(self.min_heap):
if num < -self.max_heap[0]:
heapq.heappush(self.max_heap, -num)
else:
heapq.heappush(self.min_heap, num)
elif len(self.max_heap) > len(self.min_heap):
if num < -self.max_heap[0]:
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
heapq.heappush(self.max_heap, -num)
else:
heapq.heappush(self.min_heap, num)
else:
if num > self.min_heap[0]:
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
heapq.heappush(self.min_heap, num)
else:
heapq.heappush(self.max_heap, -num)
def find_Median(self):
#rtype: float
if len(self.max_heap) == len(self.min_heap):
return (-self.max_heap[0] + self.min_heap[0]) / 2
elif len(self.max_heap) > len(self.min_heap):
return -self.max_heap[0]
else:
return self.min_heap[0]
S = Median_Finder()
S.add_Number(1)
S.add_Number(2)
result = S.find_Median()
print(result)
S.add_Number(3)
result = S.find_Median()
print(result)
S.add_Number(4)
S.add_Number(5)
result = S.find_Median()
print(result)
Sample Output:
1.5 2 3
Flowchart:
Python Code Editor:
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
Previous: Write a Python program to check if the letters of a given string can be rearranged so that two characters that are adjacent to each other are different using Heap queue algorithm.
Next: You are given two integer arrays sorted in ascending order and an integer k. Write a Python program to find k number of pairs (u, v) which consists of one element from the first array and one element from the second array using Heap queue algorithm.
What is the difficulty level of this exercise?
Test your Python skills with w3resource's quiz
Python: Tips of the Day
Checks if a string is an anagram of another string (case-insensitive, ignores spaces, punctuation and special characters)
Example:
def tips_anagram(s1, s2): _str1, _str2 = s1.replace(" ", ""), s2.replace(" ", "") return False if len(_str1) != len(_str2) else sorted(_str1.lower()) == sorted(_str2.lower()) print(tips_anagram("TRIANGLE", "INTEGRAL")) print(tips_anagram("anagram", "Nag a ram"))
Output:
True True
- New Content published on w3resource:
- Scala Programming Exercises, Practice, Solution
- Python Itertools exercises
- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework
- Angular - JavaScript Framework
- React - JavaScript Library
- Vue - JavaScript Framework
- Jest - JavaScript Testing Framework