Куча — одна из самых безобидных структур данных, когда-либо существовавших на этой планете. Почему ? Вы только посмотрите на его ограничения! Он позволяет визуализировать почти полное бинарное дерево с помощью простого массива и использует только одно условие, включающее ключи родителя и его дочерних элементов.

Тем временем наша куча:

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

Общие сведения -

Нам дан массив A с двумя атрибутами:

A.length(): дает количество элементов в массиве.

A.heap_size(): показывает, сколько элементов в куче мы имеем в данный момент.

Для Min Heap, показанного выше,

Корень находится в A[1] (мы будем использовать индексацию на основе 1)

А[] = {10, 15, 30, 40, 50, 100, 40}. Обратите внимание, что единственным применяемым условием является то, что родитель должен иметь ключ, меньший или равный ключам его дочерних элементов.

Поняв свойство кучи, теперь давайте погрузимся в алгоритм Heapsort.

Функции, необходимые для реализации пирамидальной сортировки:

  • Max_heapify()
  • Построить максимальную кучу()
  • Heapsort ()

Начнем с функции Max_Heapify(), единственная цель существования которой состоит в том, чтобы сделать узел (чья ответственность над ним возложена) быть строгим последователем свойства кучи.

Предполагается, что оба потомка узла подчиняются свойству кучи.

Он просто находит узел с максимальным ключом среди родителя, его левого потомка и правого потомка и меняет местами самый большой узел с родителем. Теперь родитель находится на правильном пути (религиозно!), но замененный дочерний элемент может начать нарушать свойство кучи. Поэтому мы снова вызываем функцию heapify() для этого узла. Узлы продолжают вызывать свои дочерние узлы, если какой-либо из них нарушает правило, и в худшем случае, да, вы правильно догадались, нам, возможно, придется пройти все дерево, что приведет к сложности O (log n) .

Важное свойство структуры кучи:

Листовые узлы начинают появляться с (n/2)+1, (n/2)+2, ….. до (n).

С учетом сказанного, теперь у нас есть возможность сделать любой узел последователем свойства кучи! Итак, давайте построимкучу .

Инициализируйте heap_size как общую длину массива. Выполните итерацию с первого нелистового узла и вызовите heapify() для каждого узла.

Итак, у нас наконец есть максимальная куча, хранящаяся в нашем массиве, готовая к обслуживанию!

Просто подумайте о временной сложности этой функции.

Ха, это легко. Поскольку мы запускаем цикл (n/2) раз и каждый раз вызываем функцию Max_heapify() (что занимает O(log n) времени), она наверняка должна занимать O(n log n).

Гм, правильно, но частично! Мы можем получить для него более точную оценку. Вот некоторые наблюдения:

  • Время работы Max_heapify() зависит от высоты узла в дереве.
  • Куча из n элементов имеет не более ceil(n/(2^(h+1))) узлов любой высоты ‘h’

Подумайте об этом.

Наконец, у нас есть достаточно инструментов, чтобы написать фактический алгоритм сортировки:

Так как у нас есть максимальная куча в наших руках, мы знаем максимальный элемент массива (хранится в корне). Поэтому мы помещаем его в самую последнюю позицию в массиве и переводим последний элемент на первую позицию. Затем мы heapify() корневой узел (после удаления последнего элемента из нашего виртуального дерева, что означает уменьшение размера кучи), чтобы убедиться, что у нас есть следующий самый большой элемент в корне. Мы снова меняем его местами с последним вторым элементом массива, и этот процесс продолжается до тех пор, пока мы не отсортируем весь массив.

Попробуйте сами, отсортируйте этот массив с помощью сортировки кучей:

A[] = { 23, 56, 10, 3, 67, 29, 78, 95, 99, 22 }

Временная сложность вышеуказанного алгоритма: O (n log n)

И вы не можете получить более точную оценку для этого случая!

Ответ на временную сложность будет рассмотрен в следующем выпуске! Ба — до свидания.