У нас на очереди популярная и столь же быстрая как предыдущая пирамидальная сортировка. Но для понимания её принципа действия нам потребуется понять, что из себя представляет такая структура данных как «Куча» (англ. Heap). Именно ей мы и посветим данную статью.
Куча представляет собой «пирамиду» из чисел. В программировании такая структура данных называется бинарное дерево.
Бинарное дерево – это структура данных дерева, в которой у каждого родительского узла может быть не больше двух потомков.
Т.о. Куча - это разновидность древовидной структуры данных для которой выполняется следующее свойство:
Все узлы в дереве больше своих потомков, то есть самый большой элемент находится в корне, и оба его потомка меньше, чем корень, и так далее. Такая куча называется - убывающая куча (Max-Heap) .
Иначе если все узлы меньше своих потомков, это называют возрастающей кучей (Min-Heap).
Рассмотрим кучу на примере Max Heap.
Обычно кучу хранят в виде одномерного массива (списка). Для примера возьмем MaxHeap с рисунка 2а. - [12, 10, 9, 5, 6, 1].
Можно заметить, что корень дерева находиться в начале списка, а потомки - на строго определенном расстоянии:
- левый потомок – 2*i + 1
- правый потомок – 2*i + 2
При этом стоит сразу отметить: дотянуться до последнего элемента по формулам потомков всегда можно из середины нашего входного массива.
Пример:
· Массив М1 длинной 100. Берем вершину на 50м месте, тогда её потомки будут на местах 101 и 102, а для элемента на 49м месте – 99 и 100.
· Массив М2 длинной 47. Берем вершину на 47//2 = 23м месте, тогда её потомки будут на местах 47 и 48, а для элемента на 22м месте – 45 и 46.
То, что в примерах мы вышли за пределы листа мы учтем далее.
Реализация на python 3.
Создадим класс «Heap» с двумя переменными объекта «heaplist» и «heapsize».
Добавим два метода heapify и buildHeap и подробно их разберем.
heapify – метод который будет непосредственно собирать\двигать числа в массиве. На вход данного метода поступает положение текущей вершины. Обозначим её переменной i.
buildHeap – метод который будет последовательно передавать в метод heapify числа из исходного массива. Метод buildHeap в качестве аргумента принимает исходный массив.
Добавление элемента
Новый элемент добавляется на последнее место в массиве, то есть позицию с индексом heapsize:
Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае следует «поднимать» новый элемент на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи:
Поиск элемента
Извлечение (удаление) элемента
Алгоритмическая сложность:
Да, я не ошибся, структуры данных тоже являются алгоритмами. Их можно назвать алгоритмами хранения (или упаковки) данных, а значит они тоже имеют свою сложность.
Операции добавления и удаления элемента требуют h операций, где h - высота кучи.
В нашей куче количество элементов на уровнях всегда не более 1 + 2 + 4, не трудно заметить, что мы получили количество элементов равное степени двойки: 1 + 2¹ + 2². Таким образом, наша глубина всегда находится в диапазоне 2ʰ⁻¹ ≤ n < 2ʰ и глубина нашего дерева равна 2. Воспользовавшись свойством логарифма получим - log₂(n), а так как сложность операций(вставка, удаление) напрямую зависит от глубины то мы получаем сложность О(log(n)). Само построение кучи занимает - O(n), т.к. мы последовательно проходимся по элементам входного массива.