TechHype
Сортировка кучей (пирамидальная) — вопросы с собеседований
Сортировка кучей особенно полезна, когда требуется сортировка большого объема данных и важна стабильная производительность.
Сортировка кучей (пирамидальная сортировка, Heap Sort) — это эффективный алгоритм сортировки, который использует структуру данных под названием куча (heap). Куча — это двоичное дерево, удовлетворяющее свойству кучи: каждый узел дерева больше (для max-кучи) или меньше (для min-кучи) своих потомков.
Сортировка кучей: принцип работы
Сортировка кучей состоит из двух основных этапов:
- Построение кучи: Массив преобразуется в кучу, где каждый родительский элемент больше или меньше своих потомков в зависимости от типа кучи. Обычно строится max-куча для сортировки по возрастанию.
- Сортировка: После того как куча построена, самый большой элемент (корень max-кучи) перемещается в конец массива, а затем структура кучи восстанавливается для оставшихся элементов. Этот процесс повторяется до тех пор, пока все элементы не будут отсортированы.
Алгоритм
- Построение кучи: Перебираются элементы массива, начиная с последнего родителя (последний элемент, который имеет потомков), и к ним применяется операция «просеивания вниз» (heapify), чтобы подчиненные узлы сохраняли структуру кучи.
- Удаление корня: После того как куча построена, корень (наибольший элемент) меняется местами с последним элементом в массиве. Далее, «просеивание вниз» применяется к новой куче (без последнего элемента) для восстановления структуры кучи.
- Повторение: Процесс продолжается, пока не останется один элемент, и весь массив оказывается отсортированным.
Пример сортировки
Допустим, у нас есть массив [4, 10, 3, 5, 1]
.
- Построение кучи:
- Применяем «просеивание вниз» и получаем max-кучу
[10, 5, 3, 4, 1]
.
- Применяем «просеивание вниз» и получаем max-кучу
- Сортировка:
- Обмениваем корень (10) с последним элементом (1) и уменьшаем размер кучи:
[1, 5, 3, 4, 10]
. - Применяем «просеивание вниз», чтобы восстановить кучу:
[5, 4, 3, 1, 10]
. - Повторяем процесс, пока весь массив не станет отсортированным.
- Обмениваем корень (10) с последним элементом (1) и уменьшаем размер кучи:
Итог: [1, 3, 4, 5, 10]
.
Вот пример реализации сортировки кучей (Heap Sort) на языке Swift:
func heapSort(_ array: inout [Int]) {
let count = array.count
// Построение кучи (перемещаем элементы в max-кучу)
for i in stride(from: count / 2 - 1, through: 0, by: -1) {
heapify(&array, count, i)
}
// Один за другим извлекаем элементы из кучи
for i in stride(from: count - 1, through: 0, by: -1) {
// Перемещаем текущий корень (максимум) в конец массива
array.swapAt(0, i)
// Восстанавливаем max-кучу для уменьшенного массива
heapify(&array, i, 0)
}
}
// Функция для преобразования поддерева с корнем i в max-кучу
func heapify(_ array: inout [Int], _ heapSize: Int, _ rootIndex: Int) {
var largest = rootIndex // Инициализируем наибольший элемент как корень
let leftChild = 2 * rootIndex + 1 // Левый ребенок
let rightChild = 2 * rootIndex + 2 // Правый ребенок
// Если левый ребенок больше корня
if leftChild < heapSize && array[leftChild] > array[largest] {
largest = leftChild
}
// Если правый ребенок больше, чем самый большой элемент на данный момент
if rightChild < heapSize && array[rightChild] > array[largest] {
largest = rightChild
}
// Если самый большой элемент не корень
if largest != rootIndex {
array.swapAt(rootIndex, largest)
// Рекурсивно преобразуем в max-кучу затронутое поддерево
heapify(&array, heapSize, largest)
}
}
// Пример использования:
var array = [4, 10, 3, 5, 1]
heapSort(&array)
print(array) // Вывод: [1, 3, 4, 5, 10]
Объяснение:
heapSort(_ array: inout [Int])
: Главная функция, которая сортирует массив. Она сначала создает max-кучу из массива, а затем последовательно извлекает максимальные элементы, помещая их в конец массива, и восстанавливает кучу для оставшихся элементов.heapify(_ array: inout [Int], _ heapSize: Int, _ rootIndex: Int)
: Вспомогательная функция, которая преобразует поддерево с корнем rootIndex в max-кучу, предполагая, что поддеревья, начинающиеся с его потомков, уже являются кучами.array.swapAt(0, i)
: Встроенная функция Swift, которая меняет местами элементы массива на указанных индексах.
Этот код реализует сортировку кучей, которая сортирует массив по возрастанию. Сначала строится max-куча, затем самые большие элементы перемещаются в конец массива, и массив преобразуется снова для оставшихся элементов.
Сложность
Временная сложность: O(n log n) в худшем, среднем и лучшем случаях.
Память: Сортировка кучей является in-place алгоритмом, т.е. не требует дополнительной памяти для хранения данных, кроме самого массива.
Сортировка кучей особенно полезна, когда требуется сортировка большого объема данных и важна стабильная производительность.
-
Аналитика магазинов3 недели назад
Тренды мобильных приложений 2025: ИИ и конфиденциальность меняют мобильную индустрию
-
Магазины приложений3 недели назад
Приложение Hot Tub появится на iOS в EC
-
Разработка4 недели назад
Смешивание цветов в SwiftUI
-
Программирование1 неделя назад
Конец программирования в том виде, в котором мы его знаем