разница между Max Heap и отсортированным стеком

Question

Я хочу знать, что когда мы можем сортировать стек с помощью метода Collections.sort, зачем нам нужна новая структура данных, такая как max heap? Спасибо

Answer 1

Стек и куча имеют совершенно разные свойства и способы использования.

Стек необходим для LIFO.Сортировка будет стоить O (N * logN), Push / pop O (1).

Heap , например, для приоритетной очереди, получение элемента min / max будет стоить O (1), вставив элемент O (log (N))

Вам необходимо определить схему и цели использования, а затем решить, что именно вам нужно.

Answer 2

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

Collections.sort - это нормально, если вам нужно отсортировать один раз. Когда вам нужно сохранять коллекцию отсортированной во время ее модификации, использование отсортированной структуры данных (например, кучи или дерева) более эффективно.

Answer 3

Это зависит от ваших требований.Схема доступа в стеке и куче совершенно другая.Стек реализован как простой список, а Heap - как приоритетная очередь.Время сортировки в стеке равно O (nlog (n)), в то время как вы можете извлечь элемент с максимальным приоритетом (Max / Min) за время O (log (n)).

Итак, ваш вопрос, где использовать MaxHeap, подумайте о сценарии, в котором вы должны найти 7-й по величине элемент из 1000. В стеке сначала нужно отсортировать, а затем 7-й от начала (по убыванию), но решениеMaxHeap вы должны извлечь элемент 7 раз, и 7-й будет решением.Так что от вашего сценария зависит, какой из них может быть лучше для вас.