Почему не стабильный капсортор?

Ответ 1

Окончательная последовательность результатов от heapsort происходит от удаления элементов из созданной кучи в чисто порядке размера (на основе поля ключа).

Любая информация о заказе элементов в исходной последовательности была потеряна во время стадии создания кучи, которая была первой.

Ответ 2

Неверный пример сортировки кучи

Рассмотрим массив 21 20a 20b 12 11 8 7 (уже в формате max-heap)

здесь 20a = 20b просто для того, чтобы различать порядок, который мы представляем им как 20a и 20b

В то время как сначала heapsort 21 удаляется и помещается в последний индекс, тогда 20a удаляется и помещается в последний, но один индекс и 20b в последний, но два индекса, поэтому после сортировки кучи массив выглядит как

7 8 11 12 20b 20a 21.

Он не сохраняет порядок элементов и, следовательно, не может быть устойчивым

Ответ 3

Стабильный означает, что если два элемента имеют один и тот же ключ, они остаются в том же порядке или положениях. Но это не относится к сортировке кучи.

Heapsort нестабилен, поскольку операции в куче могут изменить относительный порядок равных элементов.

Из здесь:

При сортировке (в порядке возрастания) heapsort сначала достигает максимума и поместите его в последний список. Итак, элемент, который имеет был выбран первым, остается последним и элементом, который был выбран второй остается на втором последнем элементе в отсортированном списке.

Опять же, процедура Build-Max-Heap работает так, что она сохраняет порядок (например: 3a, 3b) при построении кучи дерева. Для извлечения максимальный элемент также работает от корня и пытается сохранить структура дерева (кроме изменения для Heapify).

Итак, что происходит, для элементов с одинаковым значением [3a, 3b] выбирает heapsort 3a до 3b, но ставит 3a справа от 3b. Итак, поскольку список отсортированные по возрастанию, мы получаем 3b до 3a в списке.

Если вы попытаетесь использовать heapsort с (3a, 3b, 3b), тогда вы можете визуализировать ситуация.

Ответ 4

Предположим взять массив размера n (произвольное значение) и если в куче есть два последовательных элемента (предположим 15), и если их родительские индексы имеют значения, такие как 4 и 20. (это фактический порядок (.... 4,20,....., 15,15.....). Относительный порядок 4 и 1-й 15 остается таким же, но как 20 > 15, второй 15 идет вперед (своп), как определено в сортировке кучи алгоритм, относительный порядок ушел.

Ответ 5

Я знаю, что это поздние ответы, но я добавлю свои 2 цента здесь. Рассмотрим простой массив из 3 целых чисел. 2,2,2 Теперь, если вы построите максимальную кучу с помощью функции построения максимальной кучи, вы обнаружите, что массив, хранящий входные данные, не изменился, поскольку он уже находится в форме максимальной кучи. Теперь, когда мы поместили корень дерева в конец массива в первой итерации сортировки кучи, стабильность массива уже исчезла. Итак, у вас есть простой пример нестабильности сортировки кучи.

Ответ 6

Стабильные алгоритмы сортировки сортируют элементы так, что порядок повторяющихся элементов на входе также сохраняется на выходе.

Куча-сортировка включает в себя два этапа:

• Создание кучи
• Удаление и добавление корневого элемента из дерева кучи в новый массив, который будет отсортирован по порядку

1. Перерывы при создании кучи

Предположим, что входной массив равен {1, 5, 2, 3, 2, 6, 2}, и чтобы увидеть порядок 2, скажем, что это 2a, 2b и 2c, поэтому массив будет {1, 5, 2a, 3, 2b, 6, 2c}

Теперь, если вы создадите кучу (здесь min-heap), представление массива будет {1, 2b, 2a, 3, 5, 6, 2c}, где порядок 2a и 2b уже изменился.

2. Заказ перерывов при удалении корневого элемента

Теперь, когда нам нужно удалить корневой элемент (в нашем случае 1) из кучи, чтобы поместить его в другой новый массив, мы меняем его последней позицией и удаляем его оттуда, следовательно, изменяя кучу на {2c, 2b, 2a, 3, 5, 6}. Мы повторяем то же самое, и на этот раз мы удалим "2c" из кучи и поместим его в конец массива, где мы поместили "1".

Когда мы закончим повторять этот шаг, пока куча не станет пустой и каждый элемент не будет перенесен в новый массив, новый массив (отсортированный) будет выглядеть как {1, 2c, 2b, 2a, 3, 5, 6}.

Вход для сортировки кучи: {1, 5, 2a, 3, 2b, 6, 2c} → Выход: {1, 2c, 2b, 2a, 3, 5, 6}

Следовательно, мы видим, что повторяющиеся элементы (2) находятся не в том же порядке в массиве, отсортированном в куче, как они появляются на входе, и, следовательно, сортировка кучи не является стабильной!