Алгоритмы сортировки

Визуализация, проектирование и анализ алгоритма сортировки кучи.

Знать полный анализ алгоритма сортировки кучей.

Эта статья посвящена разработке, визуализации и анализу алгоритма сортировки кучей. Прочитав эту статью, вы сможете ответить на большинство вопросов, связанных с алгоритмом Heap Sort.

Что такое куча?

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

Давайте посмотрим на два разных представления кучи:

Обратите внимание, что я предполагаю, что индекс начинается с 0.

В приведенной выше куче (почти полное двоичное дерево) Parent, LeftChild и RightChild могут быть вычислены за постоянное время, поскольку это в основном одна инструкция.

Ниже приведен способ найти индекс для левого, правого и индекса родительского узла.

Parent(i)
    return ⌊(i-1)/2⌋;
--------------------------------------------------------------------
LeftChild(i)
    return 2*i+1;
--------------------------------------------------------------------
RightChild(i)
    return 2*i+2;

В приведенном выше примере кучи, если индекс узла равен i = 3, тогда индекс левого дочернего узла будет 2 * 3 + 1 = 7, а индекс правого дочернего узла будет 2 * 3 + 2 = 8.

Также обратите внимание, что высота приведенного выше дерева равна 3, а значение 8 в индексе 3 имеет высоту 1. Точно так же значение 1 в индексе 9 имеет высоту 0.

Что такое максимальная куча и минимальная куча?

Куча (почти полное двоичное дерево) называется максимальной кучей, когда родительский узел больше (или равен), чем его левый и правый дочерние узлы. На приведенном ниже рисунке вы можете видеть, что каждый родительский узел больше, чем его левый и правый дочерние узлы.

В max heap Largets элемент хранится в корне бинарного дерева.

Куча (почти полное двоичное дерево) называется минимальной кучей, когда родительский узел меньше (или равен), чем его левый и правый дочерние узлы.

В минимальной куче наименьший элемент хранится в корне бинарного дерева.

Мы будем использовать max-heap для сортировки элементов массива.

Как работает алгоритм Heapsort для сортировки по возрастанию?

  1. Построить максимальную кучу из заданного массива.
  2. На данный момент самый большой элемент хранится в корне кучи. Замените его последним элементом кучи, а затем уменьшите размер кучи на 1. Наконец, добавьте в кучу корень дерева.
  3. Теперь повторяйте шаг 2, пока размер кучи не станет больше 1.

1. Как поддерживать свойство Max-heap?

  • Мы можем сохранить свойство max-heap, вызвав метод maxHeapify на неконечных узлах. Все листовые узлы уже удовлетворяют свойству max-heap, поскольку у них нет дочерних узлов.
  • Когда метод maxHeapify вызывается с узлом, имеющим индекс «i», этот узел сравнивается с его левым и правым дочерними элементами. Найден самый большой узел среди родительского узла, левого и правого дочерних узлов, и самый большой узел заменяется родительским узлом. Поскольку родительский узел мог сместиться вниз, мы должны рекурсивно добавить в кучу левое или правое поддеревья, чтобы сохранить свойство max-heap.

Давайте посмотрим на пример наполнения узла (рассмотрим узел с индексом i=1), который нарушает свойство max-heap:

Ниже приведен фрагмент кода, который выполняет ту же работу, что и в приведенном выше примере. Читая код, постарайтесь также понять комментарии.

Давайте проанализируем временную сложность для функции maxHeapify:

  • maxHeapify включает в себя поиск самого большого индекса, что занимает постоянное количество времени на любой машине.
  • Но функция maxHeapify рекурсивно вызывается для сохранения свойства max heap в затронутом поддереве. Следовательно, в худшем случае нужно пройти от заданного узла к листу определенного поддерева. Например, если узел имеет высоту 'h', то максимальное количество рекурсивных вызовов maxHeapify() будет только 'h'.

Теперь дерево с n узлами имеет высоту logn и, следовательно, временная сложность в наихудшем случае для maxHeapify()составляетO( войти).

2. Как построить максимальную кучу из заданного массива:

  • Когда все узлы кучи удовлетворяют свойству максимальной кучи, мы можем сказать, что построили максимальную кучу.
  • Поскольку все листовые узлы кучи уже удовлетворяют свойству max heap, мы можем начать проверку свойства max heap с узла, у которого есть хотя бы один дочерний узел, и вызвать метод maxHeapify для каждого такого узла для поддержания свойство максимальной кучи.
  • Следовательно, в приведенном ниже методе buildMaxHeap инициализация цикла начинается с ((длина массива/2) — 1), а затем для каждого узла maxHeapify > метод вызывается для поддержания свойства максимальной кучи.

Давайте посмотрим на пример того, как построить максимальную кучу:

Ниже приведен код для построения максимальной кучи из заданного массива:

Анализ временной сложности функции buildMaxHeap:

  • Как видите, цикл выполняется для половины элементов массива (кучи) и для каждого узла вызывается метод maxHeapify, который занимает не более O(logn)времени. Следовательно, мы можем сказать, что buildMaxHeap займет не более O(nlogn) времени.
  • Но если вы внимательно посмотрите на приведенный выше цикл 'for', то поймете, что для каждого вызова maxHeapify значение переменной 'i' отличается, что означает, что рекурсивные вызовы maxHeapify будут иметь разную высоту для каждого узла(i). Эта высота будет равна высоте узла(i).

Теперь мы можем сказать, что наш более строгий анализ основан на свойствах n-элементной кучи, имеющей высоту ⌊ logn ⌋ и не более ⌈ n/2^(h +1)⌉узлов любой высоты h. Например, если заданная высота в куче 2 (h=2) и количество элементов в куче равно 10 (n =10), тогда куча имеет не более 2 узлов с высотой 2 (h=2). [Вы можете убедиться в этом в приведенном выше примере, который мы обсуждали ].

Если 'h' — это высота узла, то вызовов 'h' maxHeapify() будет не более. Следовательно, O(h) — это временная сложность в наихудшем случае для узла, имеющего высоту 'h', и будет не более ⌈ n/(2^ (h+1))⌉узлы высоты 'h',учитывая, что 'n' не является элементами в куче.

Суммируем все вызовы функции maxHeapify() от heighth=0до ⌊ войти ⌋:

Результат приведенного выше уравнения равен O(n). Следовательно, мы можем сказать, что временная сложность buildMaxHeap() в наихудшем случае составляет O(n) и НЕ O(nlogn).

3. Сортировка элементов массива с помощью кучи:

Как только мы будем готовы с кучей Max, мы можем перебирать элементы кучи один за другим, каждый раз меняя местами корень и последний узел кучи и уменьшая размер кучи на 1. Для каждого свопа мы должны увеличивать нашу кучу, чтобы она поддерживала свойство максимальной кучи для следующей итерации.

Поскольку корень кучи заменяется последним узлом кучи, мы должны передать индекс корня, который равен 0 для heapify и уменьшения размера кучи (то есть ' i' в приведенном ниже коде).

Теперь давайте проанализируем временную сложность Heapsort:

  • Создание максимальной кучи (метод buildMaxHeap) занимает O(n)время, как мы обсуждали выше при построении максимальной кучи.
  • Следующий цикл повторяется для каждого узла кучи и вызывает метод maxHeapify(), который каждый раз занимает не более O(logn) времени. Следовательно, heapSort имеет временную сложность как O(nlogn).

Наилучшая и наихудшая временная сложность сортировки кучей составляет O(nlogn). Она не зависит от распределения элементов массива.

4. Метод драйвера для проверки сортировки:

Чтобы протестировать приведенный выше код, давайте передадим массив со случайными числами, чтобы отсортировать их в порядке возрастания с помощью алгоритма heapSort.

Выход:

Sorted Array is :
 1 2 3 4 7 8 9 10 14 16

Является ли сортировка кучей стабильной?

Heapsort не является стабильным алгоритмом.

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

Рассмотрим массив 20 10a 10b 9 8 7 (этот массив уже имеет формат max-heap).

Здесь 10a = 10b просто чтобы различать порядок, мы представляем их как 10a и 10b .

Теперь пирамидальная сортировка сначала удаляет 20 и размещает в последнем индексе, затем 10a удаляется и помещается перед 20, а затем 10b удаляется и помещается перед 10a. Таким образом, после сортировки кучей массив выглядит следующим образом:

7 8 9 10b 10a 20.

Он не сохраняет порядок элементов (10a and 10b ) и, следовательно, нестабилен

Выполняется ли сортировка кучей на месте?

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

В этой статье все.

Подпишитесь на Викрама Гупту, чтобы найти похожий контент.

Ссылка: Введение в алгоритмы.