Алгоритм объединения нескольких отсортированных последовательностей в одну отсортированную последовательность в переполнении стека

Предположения

Следующий метод работает с любым контейнером, таким как массив, вектор, список и т. Д. Я предполагаю, что мы работаем со списками.

Давайте предположим, что у нас есть m отсортированные списки, которые мы хотим объединить.

Позволять n обозначает общее количество элементов во всех списках.

идея

Первый элемент в результирующем списке должен быть наименьшим элементом в наборе всех заголовков списков.

Идея довольно проста. Просто выберите самую маленькую головку и переместите ее из исходного списка в результат. Вы хотите повторить эту процедуру, пока есть хотя бы один непустой список. Здесь важно быстро выбрать самую маленькую голову.

Если м мало

линейное сканирование через головы O(m) в результате чего O(m * n) Общее время, которое хорошо, если m маленькая константа.

Если м не так мало

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

Нахождение минимального элемента это куча O(1), удаляя минимум O(log m) если есть m элементы в куче, и вставка элемента в кучу также O(log m),

Таким образом, для каждого из n элементы, мы вставляем его в кучу один раз и удаляем его оттуда также один раз. Общая сложность с кучей O(n log m) что значительно быстрее, чем O(n * m) если m не маленькая константа.

Резюме

Какой метод быстрее, зависит от того, сколько списков мы хотим объединить. Если m это маленький выбор линейное сканирование, в другом случае реализовать его с приоритетная очередь. Иногда трудно судить, m мал или нет, и в этом случае некоторые эксперименты будут полезны.

Я предполагаю, что без библиотек слияние. В противном случае вы должны написать собственный связанный список (это может быть вперед, или нормальный список). Отдыхай так же. Простой пример (для двух списков):

#include <list>
#include <iostream>

using namespace std;

int main(void)
{
list<int> a = { 1, 3, 5, 7, 9}, b = { 2, 4 , 6, 8, 9, 10}, c; //c is out
for(auto it1 = begin(a), it2 = begin(b); it1 != end(a) || it2 != end(b);)
if(it1 != end(a) && (it2 == end(b) || *it1 < *it2)) {
c.push_back(*it1);
++it1;
}
else {
c.push_back(*it2);
++it2;
}
for(auto x : c)
cout<<x<<' ';
cout<<'\n';
}

Результат:

1 2 3 4 5 6 7 8 9 9 10

Внимание! Вы должны скомпилировать с флагом -std = c ++ 11 (или другим с c ++ 11). Например:

g ++ -std = c ++ 11 -Wall -pedantic -Wextra -O2 d.cpp -o program.out

Сложность: Θ (n)

Память: Θ (н)

Нетрудно видеть, что каждый элемент оценивается ровно один раз в O (1), у нас есть n элементов, так что это Θ (п).

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

Сам алгоритм был описано столько раз, что нет смысла писать еще раз.

В основной задаче у нас много последовательностей, но идея та же. Вот вам обогащенный пример:

int main(void)
{
vector<vector<int> > in{{ 1, 3, 5, 7, 9}, { 2, 4 , 6, 8, 9, 10}, {2,5,7,12,10,11,18}};
vector<int> out;
typedef tuple<int, vector<int>::iterator, vector<int>::iterator> element;
priority_queue<element, vector<element>, greater<element> >  least;
for(auto& x : in) //Adding iterators to the beginning of (no empty) lists
if(!x.empty())   //and other parts of the element (value and end of vector)
least.emplace(x.front(),begin(x),end(x));

while(!least.empty()) {            //Solving
auto temp = least.top(); least.pop();
out.push_back(get<0>(temp));     //Add the smallest at the end of out
++get<1>(temp);
if(get<1>(temp) != get<2>(temp)){//If this is not the end
get<0>(temp) = *get<1>(temp);
least.push(temp);              //Update queue
}
}

for(const auto& x : out) //Print solution
cout<<x<<' ';
cout<<'\n';
}

Сложность: Θ (n log k)

Память: Θ (н)

Операции вставки и вставки находятся в O (log k), мы выполняем их n раз, так что O (n log k).

Память все еще очевидна, у нас всегда есть k элементов в priority_queue, и На) в следующей последовательности.

Код для этого может быть похож на сортировку слиянием на основе указателя и счетчика, начиная с создания «исходного» массива указателей и счетчиков для каждой последовательности и выделения второго «целевого» массива для объединения «исходного» массива указателей и рассчитывает на. Каждый проход этого алгоритма объединяет пары указателей и рассчитывает на основе последовательностей из массива «источник» в массив «пункт назначения», уменьшая количество записей в массиве примерно на 1/2. Затем указатели на массивы «источник» и «пункт назначения» меняются местами, и процесс объединения повторяется до тех пор, пока массив указателей и счетчиков не будет иметь только одну запись.

Стандартная библиотека C ++ содержит std::merge

std::vector<int> v1 { 1,2,5,7 },
v2 { 3,6,9 },
out;

std::merge(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(out));

http://en.cppreference.com/w/cpp/algorithm/merge