Является ли heapsort более эффективным при использовании на minheap или maxheap?

Question

Просто общий вопрос ....

Подтверждая название:

Является пирамидальная сортировка более эффективен при использовании на minheap или maxheap?

Примечание: Использование массива на основе реализации

Answer 1

Ниже мое взятие на нем, и я мог бы быть неправильно, но здесь идет. Теоретически они одинаково эффективны.

Куча сортировки работает в основном путем помещения всех элементов в кучу (мин.), А затем, когда они находятся в порядке кучи, многократно удаляя минимальный элемент до тех пор, пока куча не станет пустой, предоставив нам данные в порядке возрастания. Это O (nlogn), поскольку мы выполняем линейные проходы через данные, а куча поддерживает вставку/удаление log n для работы, которую мы делаем для каждого элемента данных.

Если мы использовали максимальную кучу, мы будем многократно называть getMax(). Это создает «убывающий порядок», но вы можете легко вставить эти максимальные значения справа налево в своем конечном массиве, чтобы получить все возрастающий порядок.