Максимальная куча против минимальной кучи для k-го наименьшего элемента

Question

У меня проблемы с пониманием того, почему в решениях по поиску k-го наименьшего элемента используется метод Max heap. А для k-го по величине элемента подход минимальной кучи. Разве не имеет смысла использовать min heap для поиска k-го наименьшего элемента, поскольку наименьший элемент всегда будет корневым? Поэтому, если мы хотим найти 3-й наименьший элемент, мы просто удаляем корень 2 раза, строим кучу и получаем 3-й наименьший элемент. В максимальной куче самое маленькое не в корне, так почему же лучше использовать? То же самое касается сортировки по возрастанию или убыванию чисел в массиве. Я вижу, что большинство людей используют максимальную кучу для восхождения.

Answer 1

Фактически, мы можем использовать кучи Min и Max, чтобы найти k-й наименьший элемент:

1. Так же, как вы описали, мы можем построить Min Heap, а затем извлечь k-й элемент в цикле.

или

2. Мы можем построить Max Heap всего за k элементов. Затем мы просто сравниваем остальные элементы с корнем, подставляя только те элементы корня, которые меньше корня, поэтому в Max Heap всегда есть k наименьших элементов.