Heap Sort
Последнее обновление
Пирамидальная сортировка рассматривает массив как двоичную кучу. Сначала она строит max-heap, чтобы наибольший элемент оказался в корне (индекс 0). Затем она многократно меняет корень местами с последним неотсортированным элементом - фиксируя максимум на его месте - и просеивает новый корень вниз, чтобы восстановить свойство кучи. Нажмите «воспроизвести» выше, чтобы увидеть построение кучи и извлечения.
Пирамидальная сортировка гарантирует время O(n log n), как и сортировка слиянием, но сортирует на месте, используя лишь O(1) дополнительной памяти. Она не является устойчивой и обычно хуже работает с кэшем, чем быстрая сортировка, поэтому её часто выбирают, когда важны как гарантированная граница, так и постоянная память.
Временная и пространственная сложность
| Случай | Сложность | Примечания |
|---|---|---|
| Лучший случай | O(n log n) | Построение + n извлечений |
| Средний случай | O(n log n) | Случайный порядок |
| Худший случай | O(n log n) | Гарантированно |
| Память | O(1) | На месте |
| Устойчивая | Нет | Просеивание вниз переставляет равные элементы |
Пошагово
| Шаг | Что происходит |
|---|---|
| 1 | Построить max-heap из массива (просеивать вниз, начиная с последнего родителя). |
| 2 | Поменять корень (максимум) местами с последним элементом кучи. |
| 3 | Уменьшить кучу на один - эта последняя ячейка теперь отсортирована. |
| 4 | Просеять новый корень вниз, чтобы восстановить свойство max-heap. |
| 5 | Повторять, пока в куче не останется один элемент. |
Разобранный пример
Сортировка [3, 1, 6, 5, 2, 4]. Черта | отмечает границу между уменьшающейся кучей и отсортированным хвостом:
| Проход | Массив | Действие |
|---|---|---|
| Построение кучи | [6, 5, 4, 1, 2, 3] | Просеять вниз от последнего родителя, чтобы построить max-heap; 6 теперь в корне. |
| 1 | [5, 3, 4, 1, 2 | 6] | Поменять корень 6 с последней ячейкой, уменьшить кучу и просеять 3 вниз. |
| 2 | [4, 3, 2, 1 | 5, 6] | Извлечь корень 5, затем просеять 2 вниз, чтобы 4 поднялся в корень. |
| 3 | [3, 1, 2 | 4, 5, 6] | Извлечь корень 4, затем просеять 1 вниз, чтобы 3 поднялся в корень. |
| 4 | [2, 1 | 3, 4, 5, 6] | Извлечь корень 3; 2 уже удовлетворяет свойству кучи. |
| 5 | [1 | 2, 3, 4, 5, 6] | Извлечь корень 2; остаётся один элемент, поэтому массив отсортирован. |
Когда использовать пирамидальную сортировку
| Используйте, когда | Избегайте, когда |
|---|---|
Нужен гарантированный худший случай O(n log n) без риска O(n²). | Нужна устойчивая сортировка, сохраняющая порядок равных ключей. |
Памяти мало - сортирует на месте, используя лишь O(1) дополнительной памяти. | Важна производительность кэша и данные помещаются в память - быстрая сортировка обычно быстрее. |
| Вы уже поддерживаете кучу (например, очередь с приоритетом) над данными. | Нужно наименьшее число сравнений - сортировка слиянием и быстрая сортировка на практике часто делают меньше. |
| Недоверенный ввод может спровоцировать худший случай быстрой сортировки, а рандомизировать нельзя. | Данные почти отсортированы - сортировка вставками работает на них почти за линейное время. |
Код Heap Sort
Чистая, готовая к запуску реализация Heap Sort на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Heap Sort на Python
Python
1def heap_sort(a):2 n = len(a)3 # Build a max-heap, deepest parent first4 for i in range(n // 2 - 1, -1, -1):5 sift_down(a, i, n)6 # Repeatedly move the max to the end and shrink the heap7 for end in range(n - 1, 0, -1):8 a[0], a[end] = a[end], a[0]9 sift_down(a, 0, end)10 return a11
12
13def sift_down(a, i, size):14 while True:15 largest = i16 left, right = 2 * i + 1, 2 * i + 217 if left < size and a[left] > a[largest]:18 largest = left19 if right < size and a[right] > a[largest]:20 largest = right21 if largest == i:22 return23 a[i], a[largest] = a[largest], a[i]24 i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)Код Heap Sort на JavaScript
JavaScript
1function heapSort(a) {2 const n = a.length;3 // Build a max-heap, then repeatedly move the max to the end4 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5 for (let end = n - 1; end > 0; end--) {6 [a[0], a[end]] = [a[end], a[0]];7 siftDown(a, 0, end);8 }9 return a;10}11
12function siftDown(a, i, size) {13 while (true) {14 const left = 2 * i + 1;15 const right = 2 * i + 2;16 let largest = i;17 if (left < size && a[left] > a[largest]) largest = left;18 if (right < size && a[right] > a[largest]) largest = right;19 if (largest === i) return;20 [a[i], a[largest]] = [a[largest], a[i]];21 i = largest;22 }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));Код Heap Sort на Java
Java
1import java.util.Arrays;2
3public class Main {4 static void heapSort(int[] arr) {5 int n = arr.length;6 // Build a max-heap, deepest parent first7 for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8 // Repeatedly move the max to the end and shrink the heap9 for (int end = n - 1; end > 0; end--) {10 swap(arr, 0, end);11 siftDown(arr, 0, end);12 }13 }14
15 static void siftDown(int[] arr, int i, int size) {16 while (true) {17 int largest = i, l = 2 * i + 1, r = 2 * i + 2;18 if (l < size && arr[l] > arr[largest]) largest = l;19 if (r < size && arr[r] > arr[largest]) largest = r;20 if (largest == i) return;21 swap(arr, i, largest);22 i = largest;23 }24 }25
26 static void swap(int[] arr, int a, int b) {27 int tmp = arr[a];28 arr[a] = arr[b];29 arr[b] = tmp;30 }31
32 public static void main(String[] args) {33 int[] arr = {12, 11, 13, 5, 6, 7};34 System.out.println("Before: " + Arrays.toString(arr));35 heapSort(arr);36 System.out.println("After: " + Arrays.toString(arr));37 }38}Код Heap Sort на C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11 while (true) {12 int largest = i, l = 2 * i + 1, r = 2 * i + 2;13 if (l < n && a[l] > a[largest]) largest = l;14 if (r < n && a[r] > a[largest]) largest = r;15 if (largest == i) return;16 std::swap(a[i], a[largest]);17 i = largest;18 }19}20
21void heapSort(std::vector<int>& a) {22 int n = static_cast<int>(a.size());23 // Build a max-heap in place24 for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25 // Repeatedly move the max to the end and shrink the heap26 for (int end = n - 1; end > 0; --end) {27 std::swap(a[0], a[end]);28 siftDown(a, end, 0);29 }30}31
32int main() {33 std::vector<int> data = {12, 11, 13, 5, 6, 7};34 std::cout << "Before: ";35 printVec(data);36 heapSort(data);37 std::cout << "After: ";38 printVec(data);39 return 0;40}Код Heap Sort на C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void siftDown(int a[], int n, int i) {9 while (1) {10 int largest = i, l = 2 * i + 1, r = 2 * i + 2;11 if (l < n && a[l] > a[largest]) largest = l;12 if (r < n && a[r] > a[largest]) largest = r;13 if (largest == i) return;14 int tmp = a[i];15 a[i] = a[largest];16 a[largest] = tmp;17 i = largest;18 }19}20
21void heapSort(int a[], int n) {22 // Build a max-heap in place23 for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24 // Repeatedly move the max to the end and shrink the heap25 for (int end = n - 1; end > 0; end--) {26 int tmp = a[0];27 a[0] = a[end];28 a[end] = tmp;29 siftDown(a, end, 0);30 }31}32
33int main(void) {34 int data[] = {12, 11, 13, 5, 6, 7};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 heapSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Часто задаваемые вопросы о пирамидальной сортировке
Какова временная сложность пирамидальной сортировки?
Пирамидальная сортировка составляет
O(n log n) в лучшем, среднем и худшем случаях. Построение кучи стоит O(n), а каждое из n извлечений стоит O(log n). Она использует O(1) дополнительной памяти.Устойчива ли пирамидальная сортировка?
Нет. Операция просеивания вниз может переставить равные элементы друг относительно друга, поэтому пирамидальная сортировка не сохраняет относительный порядок равных ключей.
Когда следует использовать пирамидальную сортировку?
Используйте пирамидальную сортировку, когда нужен гарантированный худший случай
O(n log n) при всего O(1) дополнительной памяти. Она избегает риска O(n²) быстрой сортировки без буфера O(n) сортировки слиянием, ценой устойчивости и производительности кэша.В чём разница между пирамидальной и быстрой сортировкой?
Обе сортируют на месте, но у быстрой сортировки худший случай
O(n²), тогда как пирамидальная гарантирует O(n log n). На практике быстрая сортировка обычно быстрее из-за лучшей локальности кэша и меньшего числа перестановок, поэтому пирамидальную выбирают в основном тогда, когда граница худшего случая должна быть гарантирована.Как пирамидальная сортировка связана с очередью с приоритетом?
Двоичная куча - это стандартная реализация очереди с приоритетом, а пирамидальная сортировка по сути состоит в многократном извлечении максимума из этой очереди. Если ваши данные уже хранятся в куче, извлечение элементов по одному даёт вам отсортированный порядок бесплатно.
Нужна ли пирамидальной сортировке max-heap или min-heap?
Чтобы сортировать по возрастанию на месте, используйте max-heap: наибольший элемент на каждом проходе меняется в конец, а отсортированный хвост растёт справа. Min-heap дал бы убывающий порядок на месте или возрастающий, если извлекать в отдельный массив.
Связанные ресурсы
Больше визуализаций
