Connect with us

TechHype

Сортировка кучей (пирамидальная) — вопросы с собеседований

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

Опубликовано

/

     
     

Сортировка кучей (пирамидальная сортировка, Heap Sort) — это эффективный алгоритм сортировки, который использует структуру данных под названием куча (heap). Куча — это двоичное дерево, удовлетворяющее свойству кучи: каждый узел дерева больше (для max-кучи) или меньше (для min-кучи) своих потомков.

Сортировка кучей: принцип работы

Сортировка кучей состоит из двух основных этапов:

  1. Построение кучи: Массив преобразуется в кучу, где каждый родительский элемент больше или меньше своих потомков в зависимости от типа кучи. Обычно строится max-куча для сортировки по возрастанию.
  2. Сортировка: После того как куча построена, самый большой элемент (корень max-кучи) перемещается в конец массива, а затем структура кучи восстанавливается для оставшихся элементов. Этот процесс повторяется до тех пор, пока все элементы не будут отсортированы.

Алгоритм

  1. Построение кучи: Перебираются элементы массива, начиная с последнего родителя (последний элемент, который имеет потомков), и к ним применяется операция «просеивания вниз» (heapify), чтобы подчиненные узлы сохраняли структуру кучи.
  2. Удаление корня: После того как куча построена, корень (наибольший элемент) меняется местами с последним элементом в массиве. Далее, «просеивание вниз» применяется к новой куче (без последнего элемента) для восстановления структуры кучи.
  3. Повторение: Процесс продолжается, пока не останется один элемент, и весь массив оказывается отсортированным.

Сортировка кучей (пирамидальная) - вопросы с собеседований

Просеивание вниз (или «heapify», или «sift down») — это операция, используемая в структуре данных «куча» (heap) для поддержания или восстановления свойства кучи. Она применяется в таких операциях, как вставка элемента в кучу, удаление элемента из кучи и при построении кучи из массива.

Основная идея

Просеивание вниз начинается с узла (родителя) и проверяет его дочерние узлы, чтобы убедиться, что родитель удовлетворяет свойству кучи:

  • Для max-кучи: Родитель должен быть больше или равен своим дочерним узлам.
  • Для min-кучи: Родитель должен быть меньше или равен своим дочерним узлам.

Если родитель не удовлетворяет этому условию, он обменивается местами с более приоритетным дочерним узлом (большим для max-кучи или меньшим для min-кучи). Этот процесс продолжается до тех пор, пока не будет восстановлено свойство кучи или не достигнуто дно дерева.

Пример сортировки

Допустим, у нас есть массив [4, 10, 3, 5, 1].

  1. Построение кучи:
    • Применяем «просеивание вниз» и получаем max-кучу [10, 5, 3, 4, 1].
  2. Сортировка:
    • Обмениваем корень (10) с последним элементом (1) и уменьшаем размер кучи: [1, 5, 3, 4, 10].
    • Применяем «просеивание вниз», чтобы восстановить кучу: [5, 4, 3, 1, 10].
    • Повторяем процесс, пока весь массив не станет отсортированным.

Итог: [1, 3, 4, 5, 10].

Вот пример реализации сортировки кучей (Heap Sort) на языке Swift:

Объяснение:

  1. heapSort(_ array: inout [Int]): Главная функция, которая сортирует массив. Она сначала создает max-кучу из массива, а затем последовательно извлекает максимальные элементы, помещая их в конец массива, и восстанавливает кучу для оставшихся элементов.
  2. heapify(_ array: inout [Int], _ heapSize: Int, _ rootIndex: Int): Вспомогательная функция, которая преобразует поддерево с корнем rootIndex в max-кучу, предполагая, что поддеревья, начинающиеся с его потомков, уже являются кучами.
  3. array.swapAt(0, i): Встроенная функция Swift, которая меняет местами элементы массива на указанных индексах.

Этот код реализует сортировку кучей, которая сортирует массив по возрастанию. Сначала строится max-куча, затем самые большие элементы перемещаются в конец массива, и массив преобразуется снова для оставшихся элементов.

Сложность

Временная сложность: O(n log n) в худшем, среднем и лучшем случаях.

Память: Сортировка кучей является in-place алгоритмом, т.е. не требует дополнительной памяти для хранения данных, кроме самого массива.

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

Если вы нашли опечатку - выделите ее и нажмите Ctrl + Enter! Для связи с нами вы можете использовать info@apptractor.ru.
Telegram

Популярное

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: