Skip to main content

Сортировка кучей

Описание

Сортировка кучей (пирамидальная сортировка) (heap sort) - это алгоритм сортировки, который является своего рода улучшением сортировки выбором. Сначала список делится на отсортированную и неотсортированную части. Затем неотсортированная часть уменьшается за счет извлечения наибольшего элемента и его перемещения в отсортированную часть. Улучшением является то, что для нахождения наибольшего элемента используется не линейный поиск, а структура данных "Куча" (см. часть 2, раздел 6).



Сложность

ЛучшееСреднееХудшееПамятьСтабильность
n log(n)n log(n)n log(n)1Нет

Реализация

// algorithms/sorting/heap-sort.js
import Sort from './sort'
import MinHeap from '../../data-structures/heap/min-heap'

export default class HeapSort extends Sort {
sort(arr) {
const _arr = []
// Создаем минимальную кучу
const minHeap = new MinHeap(this.callbacks.compareCallback)

// Добавляем элементы массива в кучу
for (const item of arr) {
this.callbacks.visitingCallback(item)

minHeap.add(item)
}

// Теперь у нас есть куча, в которой минимальный элемент всегда находится на самом верху.
// Извлекаем минимальные элементы по одному для формирования отсортированного массива
while (!minHeap.isEmpty()) {
const item = minHeap.poll()

this.callbacks.visitingCallback(item)

_arr.push(item)
}

return _arr
}
}

Тестирование

// algorithms/sorting/__tests__/heap-sort.test.js
import HeapSort from '../heap-sort'
import {
equalArr,
notSortedArr,
reverseArr,
sortedArr,
SortTester,
} from '../sort-tester'

// Константы временной сложности.
// Обратите внимание, что мы не учитываем время реструктуризации кучи,
// поэтому в реальности числа будут бОльшими
const SORTED_ARRAY_VISITING_COUNT = 40
const NOT_SORTED_ARRAY_VISITING_COUNT = 40
const REVERSE_SORTED_ARRAY_VISITING_COUNT = 40
const EQUAL_ARRAY_VISITING_COUNT = 40

describe('HeapSort', () => {
it('должен отсортировать массив', () => {
SortTester.testSort(HeapSort)
})

it('должен отсортировать массив с помощью кастомной функции сравнения', () => {
SortTester.testSortWithCustomComparator(HeapSort)
})

it('должен отсортировать отрицательные числа', () => {
SortTester.testNegativeNumbersSort(HeapSort)
})

it('должен посетить массив одинаковых элементов указанное количество раз', () => {
SortTester.testAlgorithmTimeComplexity(
HeapSort,
equalArr,
EQUAL_ARRAY_VISITING_COUNT,
)
})

it('должен посетить отсортированный массив указанное количество раз', () => {
SortTester.testAlgorithmTimeComplexity(
HeapSort,
sortedArr,
SORTED_ARRAY_VISITING_COUNT,
)
})

it('должен посетить неотсортированный массив указанное количество раз', () => {
SortTester.testAlgorithmTimeComplexity(
HeapSort,
notSortedArr,
NOT_SORTED_ARRAY_VISITING_COUNT,
)
})

it('должен посетить инвертированный отсортированный массив указанное количество раз', () => {
SortTester.testAlgorithmTimeComplexity(
HeapSort,
reverseArr,
REVERSE_SORTED_ARRAY_VISITING_COUNT,
)
})
})

Запускаем тесты:

npm run test ./algorithms/sorting/__tests__/heap-sort