Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

куча

Куча и приоритетная очередь:

Очередь с приоритетами — это абстрактный тип данных, а куча — это структура данных, поэтому куча не является очередью с приоритетами. Куча — это способ реализации очереди с приоритетами.
Существует множество способов реализации очередей с приоритетами, например массивы и связанные списки. Однако эти реализации могут гарантировать только то, что одна из операций вставки и удаления может быть завершена за время сложности O(1)O(1), в то время как другая операция должна быть завершена за O(N)O(N). временная сложность. Куча может позволить завершить операцию вставки в приоритетную очередь за временную сложность O(log N)O(logN), а операцию удаления завершить за временную сложность O(log N)O(logN). .

Куча — это особое двоичное дерево, отвечающее следующим условиям:

1. Полное бинарное дерево (узлы располагаются слева направо);
2. Значение каждого узла должно быть больше или равно или меньше или равно значению его дочернего узла.

Особенности кучи:

1. Элементы можно вставлять в кучу с временной сложностью O(logN);
2. Элементы могут быть удалены из кучи за время O(logN);
3. Максимальное или минимальное значение в куче можно получить за время сложности O(1).

Классификация кучи:

Максимальная куча: значение каждого узла в куче больше или равно значению его дочернего узла. Верхний элемент (корневой узел) максимальной кучи — это максимальное значение в куче.
Минимальная куча: значение каждого узла в куче меньше или равно значению его дочернего узла. Верхний элемент (корневой узел) минимальной кучи — это минимальное значение в куче.
Текущий номер узла — i, номер левого дочернего элемента — 2i, а номер правого дочернего узла — 2i+1.

Временная сложность и пространственная сложность

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

Теория: Сортировка кучей подразумевает использование структуры данных кучи для сортировки набора неупорядоченных элементов.

Шаги алгоритма сортировки минимальной кучи следующие:

Соберите все элементы в минимальную кучу;
Выньте и удалите верхний элемент кучи и поместите верхний элемент кучи в набор данных T, в котором хранятся упорядоченные элементы;
В это время куча будет скорректирована до нового минимального значения;
Повторяйте шаги 3 и 4, пока в куче не останется элементов;
В этот момент получается новый набор данных T, в котором элементы расположены в порядке от меньшего к большему.

Шаги алгоритма максимальной пирамидальной сортировки следующие:

Соберите все элементы в максимальную кучу;
Выньте и удалите верхний элемент кучи и поместите верхний элемент кучи в набор данных T, в котором хранятся упорядоченные элементы;
В это время куча будет скорректирована до нового максимального значения;
Повторяйте шаги 3 и 4, пока в куче не останется элементов;
В этот момент получается новый набор данных T, в котором элементы расположены в порядке от большего к меньшему.
Временная сложность: O(Nlog N). N — количество элементов в куче.

Пространственная сложность: O(N). N — количество элементов в куче.