Site icon AppTractor

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

AppTractor

Сортировка кучей (пирамидальная сортировка, 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:

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]

Объяснение:

  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 алгоритмом, т.е. не требует дополнительной памяти для хранения данных, кроме самого массива.

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

Exit mobile version