Time complexity issues with multimap

Question

I created a program that finds the median of a list of numbers. The list of numbers is dynamic in that numbers can be removed and inserted (duplicate numbers can be entered) and during this time, the new median is re-evaluated and printed out.

I created this program using a multimap because

1) the benefit of it being already being sorted,
2) easy insertion, deletion, searching (since multimap implements binary search)
3) duplicate entries are allowed.

The constraints for the number of entries + deletions (represented as N) are: 0 < N <= 100,000.

The program I wrote works and prints out the correct median, but it isn't fast enough. I know that the unsorted_multimap is faster than multimap, but then the problem with unsorted_multimap is that I would have to sort it. I have to sort it because to find the median you need to have a sorted list. So my question is, would it be practical to use an unsorted_multimap and then quick sort the entries, or would that just be ridiculous? Would it be faster to just use a vector, quicksort the vector, and use a binary search? Or maybe I am forgetting some fabulous solution out there that I haven't even thought of.

Though I'm not new to C++, I will admit, that my skills with time-complexity are somewhat medicore.

---

The more I look at my own question, the more I'm beginning to think that just using a vector with quicksort and binary search would be better since the data structures basically already implement vectors.

Answer 1

the more I look at my own question, the more I'm beginning to think that just using vector with quicksort and binary search would be better since the data structures basically already implement vectors.

If you have only few updates - use unsorted std::vector + std::nth_element algorithm which is O(N). You don't need full sorting which is O(N*ln(N)).

live demo of nth_element:

#include <algorithm>
#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>

using namespace std;

template<typename RandomAccessIterator>
RandomAccessIterator median(RandomAccessIterator first,RandomAccessIterator last)
{
   RandomAccessIterator m = first + distance(first,last)/2; // handle even middle if needed
   nth_element(first,m,last);
   return m;
}

int main()
{
   vector<int> values = {5,1,2,4,3};
   cout << *median(begin(values),end(values)) << endl;
}

Output is:

3

---

If you have many updates and only removing from middle - use two heaps as comocomocomocomo suggests. If you would use fibonacci_heap - then you would also get O(N) removing from arbitary position (if don't have handle to it).

If you have many updates and need O(ln(N)) removing from arbitary places - then use two multisets as ipc suggests.