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