Heap е една от най-невинните структури от данни, съществували някога на тази планета. Защо ? Само вижте неговите ограничения! Той ви позволява да визуализирате почти пълно двоично дърво с помощта на прост масив и използва само едно условие, включващо ключовете на родител и неговите деца.

Междувременно нашата купчина:

Тази история обхваща приложения на структура от данни на куп, използвайки псевдо кодове.

Общи подробности -

Даден ни е масив А с два атрибута -

A.length() : Дава броя на елементите в масива

A.heap_size() : представлява с колко елемента в купчината работим в момента.

За Min Heap, показан по-горе,

Коренът е в A[1] (ще използваме индексиране на база 1)

A[] = {10, 15, 30, 40, 50, 100, 40}. Забележете, че единственото приложено условие е, че родителят трябва да има ключ, по-малък или равен на ключовете на своите деца.

След като разбрахме свойството на купчините, сега нека се потопим в алгоритъма за Heapsort.

Функции, необходими за внедряване на heapsort:

  • Max_heapify()
  • Изграждане на макс. Heap()
  • Heapsort()

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

Предполага се, че и двете деца на възела се подчиняват на свойството heap.

Той просто намира възела с максимален ключ сред родителя, лявото и дясното дете и разменя най-големия с родителя. Родителят сега е на прав път (религиозно!), но размененото дете може да започне да нарушава свойството на купчината. Следователно, ние отново извикваме функцията heapify() за този възел. Възлите продължават да извикват дъщерния си възел, ако някой от тях наруши правилото, и в най-лошия случай, да, добре познахте, може да се наложи да преминем през цялото дърво, което води до сложност от O (log n) .

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

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

С това казано, сега имаме властта да направим всеки възел последовател на свойството heap! Така че нека изградимкупчина.

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

Така че най-накрая имаме максимална купчина, съхранена в нашия масив, готова за обслужване!

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

Ха, лесно е. Тъй като изпълняваме цикъл за (n/2) пъти и извикваме функцията Max_heapify() всеки път (което отнема O(log n) време), трябва да отнема O(n log n) със сигурност.

Хм, правилно, но отчасти! Можем да изведем по-строга граница за него. Ето някои наблюдения:

  • Времето за изпълнение на Max_heapify() варира в зависимост от височината на възела в дървото.
  • Купчина от n елемента има най-много ceil(n/(2^(h+1))) възли с произволна височина ‘h’

Помислете върху това.

Най-накрая имаме достатъчно инструменти, за да напишем действителния алгоритъм за сортиране:

Тъй като имаме максимален куп в ръцете си, ние знаем максималния елемент на масива (съхранен в root). Така че го поставяме на последната позиция в масива и поставяме последния елемент на първа позиция. След това ние heapify() основен възел (след премахване на последния елемент от нашето виртуално дърво, което означава, чрез намаляване на heap_size), за да гарантираме, че имаме следващия най-голям елемент в корена. Отново го разменяме с последния втори елемент от масива и този процес продължава, докато сортираме целия масив.

Опитайте сами, сортирайте този масив с помощта на heap sort:

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

Времева сложност на горния алгоритъм: O(n log n)

И не можете да получите по-строга граница за този случай!

Отговорът за времевата сложност ще бъде разгледан в следващото издание! Ба — Чао.