Question

Given a set of keys, the median key is the key in the "middle". When the number of keys is odd. the middle key is unique. However, when the number of keys is even, there are two middle keys. We call one the lower median key and the other the upper median key. Design an ADT that supports the following methods: When the ADT has n items, your implementation for the three methods should run in O(log n) time. When n is even, the items to return for RemoveLowerMedian() and RemoveUpperMedian() are obvious. When n is odd, let these methods simply return the item with the median key.

Answer 1

this is a common question for the heap data structure.

we maintain a max and min heap in the following way - After processing an incoming element, the number of elements in heaps differ utmost by 1 element. When both heaps contain same number of elements, we pick average of heaps root data as effective median. When the heaps are not balanced, we select effective median from the root of heap containing more elements.

example

for 5 -> 5

for 5,15 -> 5 and 15

for 5,15,1 -> 5

---------------------------------------------------------

code

#include<iomanip>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>

using namespace std;
int main(void)
{
   priority_queue<int> max_heap;
   priority_queue< int, vector <int>, greater <int> > min_heap;
   long long i,n,k;
   cin>>n;
   cin>>k;
   max_heap.push(k);
   n--;
   double a = max_heap.top();
   cout<<fixed<<setprecision(1)<<a<<endl;
   while(n--)
   {
       /*inserting*/

       cin>>k;
       if(k >= max_heap.top())
       {
               min_heap.push(k);
       }
       else if(min_heap.empty())
       {
           min_heap.push(max_heap.top());
           max_heap.pop();
           max_heap.push(k);

       }
       else
           max_heap.push(k);

       /*balancing*/

       if(abs(max_heap.size() - min_heap.size()) > 1)
       {
           if(max_heap.size() > min_heap.size())
           {
               min_heap.push(max_heap.top());
               max_heap.pop();
           }
           else
           {
               max_heap.push(min_heap.top());
               min_heap.pop();
           }
       }

       /* finding the median */

       if( (min_heap.size() + max_heap.size())%2 == 0)
       {
           cout<<min_heap.top()<<" "<<max_heap.top()<<endl;
       }
       else if(min_heap.size() > max_heap.size())
       {
           double ans = min_heap.top();
           cout<<fixed<<setprecision(1)<<ans<<endl;

       }
       else
       {
           double ans = max_heap.top();
           cout<<fixed<<setprecision(1)<<ans<<endl;   
               }
   }
}

---------------------------------------------------------------

this is my code for this!

sample run -

input -
//first input the total number of elements
6

//now the elements one by one
12
4
5
3
8
7

output -

12

4 12

5

4 5

5

5 7

-----------------------------------------------------------

thank you!

note - try and do this yourself, will really help you to learn