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

Tip

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

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

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

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

11.7.1 Алгоритм¶

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

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

Tip

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

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

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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)\) памяти. Обмен элементов и операции просеивания выполняются прямо в исходном массиве.
Нестабильная сортировка: при обмене вершины кучи и нижнего элемента относительный порядок равных элементов может измениться.

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

11.7.1 Алгоритм¶

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

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