Сортировка очереди в O(n журнал n) с использованием не более 2 очередей

#algorithm #data-structures

Вопрос:

Нам было поручено отсортировать очередь в O(n log n), используя базовые функции, такие как очередь, удаление очереди, просмотр, только пусто. Кроме того, мы можем использовать другую очередь, чтобы помочь нам. Никакие другие структуры данных не допускаются.

Возникли проблемы с поиском решения, поскольку я чувствую, что это, возможно, модификация проблемы «разделяй и властвуй», но я не могу найти решение с использованием 4 основных функций.

Можно ли получить какие-то подсказки для решения этой проблемы?

1. Под очередью и снятием с очереди вы подразумеваете базовое нажатие и нажатие?

2. Ага, очередь == толчок и удаление из очереди == поп

3. Ага. Например, очередь, q, с элементами {1, 2, 3, 4}. q.нажмите(5), элементы = {1, 2, 3, 4 ,5} q.pop(), элементы = {2, 3, 4, 5}

4. Вы можете выполнить сортировку слиянием с помощью очередей.

5. Разрешены ли какие-либо переменные, кроме 2 очередей?

Ответ №1:

Учитывая, что очередь A заполнена, а очередь B пуста, если A состоит из отсортированных групп элементов w, вы можете объединить их попарно, чтобы получить отсортированную группу элементов 2w следующим образом:

В то время как(A. длина — B. длина > w), извлеките элементы w из A и поместите их в B. A и B будут состоять из отсортированных групп элементов >w, плюс некоторые оставшиеся.
несколько раз извлекайте элементы w как из A, так и из B, объединяя их на задней панели A, чтобы создать упорядоченные группы элементов 2w. Остановитесь, когда все элементы будут обработаны (будьте осторожны, чтобы не извлекать элементы из A, которые вы уже обработали. Вам нужно будет запомнить его первоначальный размер). Затем A будет состоять из отсортированных групп 2w, а B снова будет пустым.

Повторите описанную выше процедуру с w=1 (группы по 1 всегда сортируются), затем w=2, w=4 … w=2ⁿ и т.д., Пока вся очередь не будет отсортирована.