Какова временная сложность сортировки половины массива с использованием очереди приоритетов?

Question

Итак, я разработал очередность приоритетов, используя Min Heap, и в соответствии с онлайн-учебниками для сортировки всего массива с использованием очереди приоритетов требуется время O (nlogn). Это происходит потому, что мы извлекаем «n» раз, и для каждого извлечения мы должны выполнить исправление приоритета, которое занимает время входа в систему. Следовательно, это невозможно.

Однако, если я хочу только отсортировать половину массива каждый раз, будет ли это еще время O (nlogn)? Или это будет просто O (logn)? Причина, по которой я хочу сделать это, - это то, что я хочу получить элемент со средним приоритетом, и это похоже на единственный способ сделать это, используя очередь приоритетов, извлекая половину элементов, если нет более интуитивного способа получить элемент с средний приоритет в очереди приоритетов.

Answer 1

Я думаю, что вопрос состоит из двух частей, так что я буду отвечать на две части:

(а) Если я вас правильно понял, сортировкой «половина массива» вы имеете в виду получение отсортированного массива (n/2) наименьшие значения данного массива. Это должно будет занять время O (n lg n). Если бы была методика для этого меньше времени O (n lg n), тогда всякий раз, когда мы хотели отсортировать массив из n значений, максимальное значение которых известно как v (и мы можем получить максимальное значение в O (n) время), мы могли бы построить массив из 2n элементов, где первая половина будет исходным массивом, а вторая половина заполнена значением, большим v. Затем, применяя гипотетический метод, мы могли бы сортировать исходный массив в время меньше, чем O (n lg n), что, как известно, невозможно.

(b) Но если я правильно понимаю «элемент со средним приоритетом» в качестве медианного элемента в массиве, вы можете быть заинтересованы в this question.