Придумать Алгоритм

Polyphem

Помогите пожалуйста придумать алгоритм, который из k упорядоченных по возрастанию списков делает один упорядоченный по возрастанию за время O(n*log(k где n - общее количество элементов в списках. Не получается придумать именно за такое время.

Dallas

Нужна структура данных, позволяющая туда добавлять элементы и вынимать минимальные за время O(log k где k - количество элементов в данный момент времени в этой структуре. В качестве такой структуры пойдёт какое-нибудь сбалансированное АВЛ-дерево (в поиск).
А теперь сам алгоритм. Сначала пихаешь в эту структуру все минимальные элементы в списках. Потом на каждом следующем шаге вынимаешь из структуры минимальный элемент и добавляешь в неё следующий по порядку элемент того списка, из которого был этот элемент (если этот список ещё не закончился). Вот и всё, последовательность вынимаемых элементов - то что надо.
Если не учитывать времени работы с адресами памяти, то сложность получится как раз O(n*log k).

Polyphem

Спасибо.

andy_null

Нужна структура данных, позволяющая туда добавлять элементы и вынимать минимальные за время O(log k)
Для этой задачи куча (heap) будет быстрее и проще для понимания
Оставить комментарий
Имя или ник:
Комментарий: