Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 11.7 Пирамидальная сортировка

Tip

Перед чтением этого раздела убедитесь, что вы уже изучили главу «Куча».

Пирамидальная сортировка (heap sort) - это эффективный алгоритм сортировки, основанный на структуре данных «куча». Для его реализации можно использовать уже изученные нами «построение кучи» и «извлечение элементов из кучи».

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

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

## 11.7.1 Алгоритм

Пусть длина массива равна \(n\). Тогда процесс пирамидальной сортировки показан на рисунке 11-12.

1. Подать на вход массив и построить из него макс-кучу. После этого максимальный элемент окажется в вершине кучи.
2. Обменять элемент в вершине кучи (первый элемент) с элементом внизу кучи (последний элемент). После обмена длина кучи уменьшается на \(1\) , а число уже отсортированных элементов увеличивается на \(1\) .
3. Начиная с вершины, выполнить операцию просеивания сверху вниз. После этого свойство кучи будет восстановлено.
4. Циклически повторять шаг `2.` и шаг `3.` . После \(n - 1\) раундов массив будет полностью отсортирован.

Tip

На самом деле операция извлечения из кучи тоже включает шаг `2.` и шаг `3.` , только дополнительно содержит действие по удалению элемента.

<1><2><3><4><5><6><7><8><9><10><11><12>

Рисунок 11-12 Шаги пирамидальной сортировки

В коде используется та же функция просеивания сверху вниз `sift_down()`, что и в главе «Куча». Важно помнить, что длина кучи уменьшается по мере извлечения максимального элемента, поэтому функции `sift_down()` нужно передавать параметр длины \(n\) , чтобы указать текущую действительную длину кучи. Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
heap_sort.py

    def sift_down(nums: list[int], n: int, i: int):
        """Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз"""
        while True:
            # Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            l = 2 * i + 1
            r = 2 * i + 2
            ma = i
            if l < n and nums[l] > nums[ma]:
                ma = l
            if r < n and nums[r] > nums[ma]:
                ma = r
            # Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if ma == i:
                break
            # Поменять два узла местами
            nums[i], nums[ma] = nums[ma], nums[i]
            # Циклическое просеивание вниз
            i = ma

    def heap_sort(nums: list[int]):
        """Сортировка кучей"""
        # Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for i in range(len(nums) // 2 - 1, -1, -1):
            sift_down(nums, len(nums), i)
        # Извлекать максимальный элемент из кучи в течение n-1 итераций
        for i in range(len(nums) - 1, 0, -1):
            # Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            nums[0], nums[i] = nums[i], nums[0]
            # Начиная с корневого узла, выполнить просеивание сверху вниз
            sift_down(nums, i, 0)

heap_sort.cpp

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(vector<int> &nums, int n, int i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int ma = i;
            if (l < n && nums[l] > nums[ma])
                ma = l;
            if (r < n && nums[r] > nums[ma])
                ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i) {
                break;
            }
            // Поменять два узла местами
            swap(nums[i], nums[ma]);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

    /* Сортировка кучей */
    void heapSort(vector<int> &nums) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for (int i = nums.size() / 2 - 1; i >= 0; --i) {
            siftDown(nums, nums.size(), i);
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for (int i = nums.size() - 1; i > 0; --i) {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            swap(nums[0], nums[i]);
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums, i, 0);
        }
    }

heap_sort.java

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(int[] nums, int n, int i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int ma = i;
            if (l < n && nums[l] > nums[ma])
                ma = l;
            if (r < n && nums[r] > nums[ma])
                ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i)
                break;
            // Поменять два узла местами
            int temp = nums[i];
            nums[i] = nums[ma];
            nums[ma] = temp;
            // Циклическое просеивание вниз
            i = ma;
        }
    }

    /* Сортировка кучей */
    void heapSort(int[] nums) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for (int i = nums.length - 1; i > 0; i--) {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums, i, 0);
        }
    }

heap_sort.cs

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    void SiftDown(int[] nums, int n, int i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int ma = i;
            if (l < n && nums[l] > nums[ma])
                ma = l;
            if (r < n && nums[r] > nums[ma])
                ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i)
                break;
            // Поменять два узла местами
            (nums[ma], nums[i]) = (nums[i], nums[ma]);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

    /* Сортировка кучей */
    void HeapSort(int[] nums) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for (int i = nums.Length / 2 - 1; i >= 0; i--) {
            SiftDown(nums, nums.Length, i);
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for (int i = nums.Length - 1; i > 0; i--) {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            (nums[i], nums[0]) = (nums[0], nums[i]);
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            SiftDown(nums, i, 0);
        }
    }

heap_sort.go

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    func siftDown(nums *[]int, n, i int) {
        for true {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            l := 2*i + 1
            r := 2*i + 2
            ma := i
            if l < n && (*nums)[l] > (*nums)[ma] {
                ma = l
            }
            if r < n && (*nums)[r] > (*nums)[ma] {
                ma = r
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if ma == i {
                break
            }
            // Поменять два узла местами
            (*nums)[i], (*nums)[ma] = (*nums)[ma], (*nums)[i]
            // Циклическое просеивание вниз
            i = ma
        }
    }

    /* Сортировка кучей */
    func heapSort(nums *[]int) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for i := len(*nums)/2 - 1; i >= 0; i-- {
            siftDown(nums, len(*nums), i)
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for i := len(*nums) - 1; i > 0; i-- {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            (*nums)[0], (*nums)[i] = (*nums)[i], (*nums)[0]
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums, i, 0)
        }
    }

heap_sort.swift

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    func siftDown(nums: inout [Int], n: Int, i: Int) {
        var i = i
        while true {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            let l = 2 * i + 1
            let r = 2 * i + 2
            var ma = i
            if l < n, nums[l] > nums[ma] {
                ma = l
            }
            if r < n, nums[r] > nums[ma] {
                ma = r
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if ma == i {
                break
            }
            // Поменять два узла местами
            nums.swapAt(i, ma)
            // Циклическое просеивание вниз
            i = ma
        }
    }

    /* Сортировка кучей */
    func heapSort(nums: inout [Int]) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for i in stride(from: nums.count / 2 - 1, through: 0, by: -1) {
            siftDown(nums: &nums, n: nums.count, i: i)
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for i in nums.indices.dropFirst().reversed() {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            nums.swapAt(0, i)
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums: &nums, n: i, i: 0)
        }
    }

heap_sort.js

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    function siftDown(nums, n, i) {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            let l = 2 * i + 1;
            let r = 2 * i + 2;
            let ma = i;
            if (l < n && nums[l] > nums[ma]) {
                ma = l;
            }
            if (r < n && nums[r] > nums[ma]) {
                ma = r;
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma === i) {
                break;
            }
            // Поменять два узла местами
            [nums[i], nums[ma]] = [nums[ma], nums[i]];
            // Циклическое просеивание вниз
            i = ma;
        }
    }

    /* Сортировка кучей */
    function heapSort(nums) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for (let i = nums.length - 1; i > 0; i--) {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            [nums[0], nums[i]] = [nums[i], nums[0]];
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums, i, 0);
        }
    }

heap_sort.ts

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    function siftDown(nums: number[], n: number, i: number): void {
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            let l = 2 * i + 1;
            let r = 2 * i + 2;
            let ma = i;
            if (l < n && nums[l] > nums[ma]) {
                ma = l;
            }
            if (r < n && nums[r] > nums[ma]) {
                ma = r;
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma === i) {
                break;
            }
            // Поменять два узла местами
            [nums[i], nums[ma]] = [nums[ma], nums[i]];
            // Циклическое просеивание вниз
            i = ma;
        }
    }

    /* Сортировка кучей */
    function heapSort(nums: number[]): void {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for (let i = nums.length - 1; i > 0; i--) {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            [nums[0], nums[i]] = [nums[i], nums[0]];
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums, i, 0);
        }
    }

heap_sort.dart

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(List<int> nums, int n, int i) {
      while (true) {
        // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma]) ma = l;
        if (r < n && nums[r] > nums[ma]) ma = r;
        // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
        if (ma == i) break;
        // Поменять два узла местами
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // Циклическое просеивание вниз
        i = ma;
      }
    }

    /* Сортировка кучей */
    void heapSort(List<int> nums) {
      // Построение кучи: выполнить heapify для всех узлов, кроме листовых
      for (int i = nums.length ~/ 2 - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
      }
      // Извлекать максимальный элемент из кучи в течение n-1 итераций
      for (int i = nums.length - 1; i > 0; i--) {
        // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // Начиная с корневого узла, выполнить просеивание сверху вниз
        siftDown(nums, i, 0);
      }
    }

heap_sort.rs

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    fn sift_down(nums: &mut [i32], n: usize, mut i: usize) {
        loop {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            let l = 2 * i + 1;
            let r = 2 * i + 2;
            let mut ma = i;
            if l < n && nums[l] > nums[ma] {
                ma = l;
            }
            if r < n && nums[r] > nums[ma] {
                ma = r;
            }
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if ma == i {
                break;
            }
            // Поменять два узла местами
            nums.swap(i, ma);
            // Циклическое просеивание вниз
            i = ma;
        }
    }

    /* Сортировка кучей */
    fn heap_sort(nums: &mut [i32]) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for i in (0..nums.len() / 2).rev() {
            sift_down(nums, nums.len(), i);
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for i in (1..nums.len()).rev() {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            nums.swap(0, i);
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            sift_down(nums, i, 0);
        }
    }

heap_sort.c

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    void siftDown(int nums[], int n, int i) {
        while (1) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            int ma = i;
            if (l < n && nums[l] > nums[ma])
                ma = l;
            if (r < n && nums[r] > nums[ma])
                ma = r;
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i) {
                break;
            }
            // Поменять два узла местами
            int temp = nums[i];
            nums[i] = nums[ma];
            nums[ma] = temp;
            // Циклическое просеивание вниз
            i = ma;
        }
    }

    /* Сортировка кучей */
    void heapSort(int nums[], int n) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for (int i = n / 2 - 1; i >= 0; --i) {
            siftDown(nums, n, i);
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for (int i = n - 1; i > 0; --i) {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums, i, 0);
        }
    }

heap_sort.kt

    /* Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз */
    fun siftDown(nums: IntArray, n: Int, li: Int) {
        var i = li
        while (true) {
            // Определить узел с максимальным значением среди i, l и r и обозначить его как ma
            val l = 2 * i + 1
            val r = 2 * i + 2
            var ma = i
            if (l < n && nums[l] > nums[ma])
                ma = l
            if (r < n && nums[r] > nums[ma])
                ma = r
            // Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
            if (ma == i)
                break
            // Поменять два узла местами
            val temp = nums[i]
            nums[i] = nums[ma]
            nums[ma] = temp
            // Циклическое просеивание вниз
            i = ma
        }
    }

    /* Сортировка кучей */
    fun heapSort(nums: IntArray) {
        // Построение кучи: выполнить heapify для всех узлов, кроме листовых
        for (i in nums.size / 2 - 1 downTo 0) {
            siftDown(nums, nums.size, i)
        }
        // Извлекать максимальный элемент из кучи в течение n-1 итераций
        for (i in nums.size - 1 downTo 1) {
            // Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
            val temp = nums[0]
            nums[0] = nums[i]
            nums[i] = temp
            // Начиная с корневого узла, выполнить просеивание сверху вниз
            siftDown(nums, i, 0)
        }
    }

heap_sort.rb

    ### Длина кучи равна n; начиная с узла i, выполнить просеивание сверху вниз ###
    def sift_down(nums, n, i)
      while true
        # Определить узел с максимальным значением среди i, l и r и обозначить его как ma
        l = 2 * i + 1
        r = 2 * i + 2
        ma = i
        ma = l if l < n && nums[l] > nums[ma]
        ma = r if r < n && nums[r] > nums[ma]
        # Если узел i уже максимален или индексы l и r вне границ, дальнейшее просеивание не требуется, выйти
        break if ma == i
        # Поменять два узла местами
        nums[i], nums[ma] = nums[ma], nums[i]
        # Циклическое просеивание вниз
        i = ma
      end
    end

    ### Сортировка кучей ###
    def heap_sort(nums)
      # Построение кучи: выполнить heapify для всех узлов, кроме листовых
      (nums.length / 2 - 1).downto(0) do |i|
        sift_down(nums, nums.length, i)
      end
      # Извлекать максимальный элемент из кучи в течение n-1 итераций
      (nums.length - 1).downto(1) do |i|
        # Поменять корневой узел с самым правым листом местами (поменять первый и последний элементы)
        nums[0], nums[i] = nums[i], nums[0]
        # Начиная с корневого узла, выполнить просеивание сверху вниз
        sift_down(nums, i, 0)
      end
    end

Визуализация кода

Во весь экран >

## 11.7.2 Характеристики алгоритма

- Временная сложность равна \(O(n \log n)\), алгоритм не является адаптивным: построение кучи занимает \(O(n)\) времени. Извлечение максимального элемента из кучи имеет временную сложность \(O(\log n)\) и выполняется \(n - 1\) раз.
- Пространственная сложность равна \(O(1)\), сортировка выполняется на месте: несколько переменных-указателей используют \(O(1)\) памяти. Обмен элементов и операции просеивания выполняются прямо в исходном массиве.
- Нестабильная сортировка: при обмене вершины кучи и нижнего элемента относительный порядок равных элементов может измениться.

##### Оставляйте свои идеи, вопросы и предложения в комментариях