Проблемы временной сложности с Multimap

Если ваша цель - отслеживать медианное значение на лету, когда элементы вставляются / удаляются, вы должны использовать min-heap и max-heap. Каждый из них будет содержать половину элементов ... Пару дней назад был связанный с этим вопрос: Как реализовать медианную кучу

Хотя, если вам нужно искать определенные значения, чтобы удалить элементы, вам все равно понадобится какая-то карта.

Вы сказали, что это медленно. Вы выполняете итерацию от начала карты до элемента (N / 2) каждый раз, когда вам нужна медиана? Тебе это не нужно. Вы можете отслеживать медиану, постоянно указывая на него итератор, а также счетчик количества элементов, меньших этого. Каждый раз, когда вы вставляете / удаляете, сравнивайте новый / старый элемент со средним значением и обновляйте итератор и счетчик.

Другой способ увидеть это как две мультиотображения, каждая из которых содержит половину элементов. Один содержит элементы меньше медианы (или равные), а другой - больше. Кучи делают это более эффективно, но не поддерживают поиск.

Если вам нужна медиана всего несколько раз, вы можете использовать алгоритм «выбора». Это описано в книге Седжвика. В среднем это занимает O (n) времени. Это похоже на быструю сортировку, но не выполняет сортировку полностью. Он просто разбивает массив на части со случайными поворотами, пока, в конце концов, он не «выберет» с одной стороны m меньших элементов (m = (n + 1) / 2). Затем вы ищете наибольший из этих m элементов, и это медиана.

чем больше я смотрю на свой вопрос, тем больше я начинаю думать, что было бы лучше просто использовать вектор с быстрой сортировкой и двоичным поиском, поскольку структуры данных в основном уже реализуют векторы.

Если у вас мало обновлений - используйте несортированный std :: vector + std :: nth_element алгоритм, который является O (N). Вам не нужна полная сортировка, которая составляет O (N * ln (N)).

живая демонстрация 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;
}

Выход:

3

Если у вас много обновлений и вы удаляете их только из середины, используйте две кучи, как comocomocomocomo предлагает. Если бы вы использовали fibonacci_heap - тогда вы также получите удаление O (N) из произвольной позиции (если у вас нет дескриптора).

Если у вас много обновлений и вам нужно удалить O (ln (N)) из произвольных мест - тогда используйте два мультимножества как ipc предлагает .

Вот как это можно реализовать в O(log N) за обновление:

template <typename T>
class median_set {
public:
  std::multiset<T> below, above;

  // O(log N)
  void rebalance()
  {
    int diff = above.size() - below.size();
    if (diff > 0) {
      below.insert(*above.begin());
      above.erase(above.begin());
    } else if (diff < -1) {
      above.insert(*below.rbegin());
      below.erase(below.find(*below.rbegin()));
    }
  }

public:
  // O(1)
  bool empty() const { return below.empty() && above.empty(); }

  // O(1)
  T const& median() const
  {
    assert(!empty());
    return *below.rbegin();
  }

  // O(log N)
  void insert(T const& value)
  {
    if (!empty() && value > median())
      above.insert(value);
    else
      below.insert(value);
    rebalance();
  }

  // O(log N)
  void erase(T const& value)
  {
    if (value > median())
      above.erase(above.find(value));
    else
      below.erase(below.find(value));
    rebalance();
  }
};

(Работа с тестами в действии)

Идея такая:

• Следите за значениями выше и ниже медианы в двух наборах
• Если добавлено новое значение, добавьте его в соответствующий набор. Всегда следите за тем, чтобы в нижеследующем наборе ровно на 0 или 1 больше, чем в другом.
• Если значение удалено, удалите его из набора и убедитесь, что условие все еще выполняется.

Вы не можете использовать priority_queues, потому что они не позволят вам удалить один элемент.

Вам почти наверняка лучше использовать вектор. Возможно сохранение вспомогательного вектора индексов, который будет удаляться между расчетами медианы, чтобы вы могли удалять их партиями. Новые дополнения также можно поместить во вспомогательный вектор, отсортировать, а затем объединить.