Given: A sequence of numbers x1, x2, ..., xn input one-by-one, find the median a
ID: 3905838 • Letter: G
Question
Given: A sequence of numbers x1, x2, ..., xn input one-by-one, find the median as the numbers arrive.
Language C++
Solution implemented using a min-heap and max-heap that holds the bottom half and top half of the numbers respectively.
Heaps are implemented using the priority_queue container from the STL
The test function is provided below. Also included is a function print_queue if you need to view the contents of the heaps at any point.
#include
#include
#include
using namespace std;
const int MAX_VAL = 100;
const int NUM_ELEM = 15;
int find_median(priority_queue, greater>& h_high, priority_queue& h_low, int num);
template void print_queue(T& q);
int main() {
int current_median;
priority_queue lo; // Bottom half of numbers - max-heap (default)
priority_queue, greater > hi; // Top half of numbers - min-heap
srand(time(0)); // Seed for random number generator
for (int i = 0; i < NUM_ELEM; i++) {
int n = rand() % MAX_VAL;
current_median = find_median(hi, lo, n);
cout << "Inserted " << n << " Median " << current_median << endl << endl;
}
return 0;
}
template void print_queue(T& q) {
T q_copy(q);
while(!q_copy.empty()) {
std::cout << q_copy.top() << " ";
q_copy.pop();
}
std::cout << ' ';
}
int find_median(priority_queue, greater>& h_high, priority_queue& h_low, int num) {
// Your code here...
}
Explanation / Answer
solution :
Here three conditions may arise as in case of heap, we may face three possible cases:
case 1: when the left side of the heap has more elements than the right-hand side
case 2: when both sides have an equal number of elements.
case 3: when the right size of the heap has more elements than the left side.
Accordingly, we are going to use nested if-else condition for it.
void median(double n,double &median)
{
if (Max_Heap_Left.length() > Min_Heap_Right.length())
{
if (n < median)
{
Min_Heap_Right.push(Max_Heap_Left.top());
Max_Heap_Left.pop();
Max_Heap_Left.push(n);
}
else
Min_Heap_Right.push(n);
median = ((double)Max_Heap_Left.top()
+(double)Min_Heap_Right.top())/2.0;
}
else if (Max_Heap_Left.length()==Min_Heap_Right.length())
{
if (n < median)
{
Max_Heap_Left.push(n);
median = (double)Max_Heap_Left.top();
}
else
{
Min_Heap_Right.push(x);
median = (double)Min_Heap_Right.top();
}
}
else
{
if (n > median)
{
Max_Heap_Left.push(Min_Heap_Right.top());
Min_Heap_Right.pop();
Min_Heap_Right.push(n);
}
else
Max_Heap_Left.push(x);
median = ((double)Max_Heap_Left.top()
+ (double)Min_Heap_Right.top())/2.0;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.