Хеапсорт Тиме Цомплекити

Хрпа се назива „делимично уређена“, а не „делимично сортирана“. Реч 'сорт' значи потпуно сређивање (потпуно сортирање). Хрпа није делимично уређена произвољно. Хрпа је делимично уређена према критеријуму (обрасци), као што је приказано испод.

Дакле, хеапсорт се састоји од две фазе: прављење гомиле и издвајање наређеног елемента са врха гомиле. У другој фази, након сваке екстракције, гомила се поново гради. Свака реконструкција је бржа од првобитног процеса изградње, пошто се реконструкција врши из претходне градње, где је један елемент уклоњен. И уз то, хеапсорт сортира потпуно несортирану листу.

Циљ овог чланка је да укратко објасни хеапсорт, а затим произведе његову временску сложеност (погледајте значење временске сложености у наставку). Пред крај, кодирање се ради у Ц++.

Минимална хрпа

Хрпа може бити минимална или максимална гомила. Максимална гомила је она у којој је први елемент највиши елемент, а цело стабло или одговарајућа листа је делимично поређана у опадајућем редоследу. Мин-хеап је онај где је први елемент најмањи елемент, а цела листа је делимично поредана у растућем редоследу. У овом чланку се разматра само минимална гомила. Напомена: у теми гомиле, елемент се назива и чвор.

Хрпа је потпуно бинарно стабло. Бинарно стабло се може изразити као низ (листа); читати одозго на доле и с лева на десно. Својство гомиле за мин-хеап је да је родитељски чвор мањи или једнак сваком од своја два детета. Пример неуређене листе је:

Први ред ове табеле су елементи низа. У другом реду су индекси засновани на нули. Ова листа елемената може се изразити као дрво. Нулти елементи су додати да се направи пуно бинарно стабло. Строго говорећи, нулти елементи нису део листе (стабла). Ова листа нема ред, тако да још није гомила. Постат ће гомила када има делимично поређање, према својству гомиле.

Однос између чворова и индекса

Запамтите, гомила је комплетно бинарно стабло пре него што има конфигурацију гомиле (својство гомиле). Претходна листа још увек није гомила, јер се елементи не повинују својству гомиле. Постаје гомила након преуређења елемената у делимичан ред према својству мин-хеап. Делимичан редослед се може посматрати као делимично сортирање (иако реч „сорт” значи потпуно сређивање).

Без обзира да ли је бинарно стабло гомила или не, сваки родитељ има два детета, осим листова (последњих) чворова. Између сваког родитеља и његове деце постоји математичка веза између индекса. То је следеће: Ако је родитељ на индексу и, онда је лево дете на индексу:

а право дете је на индексу:

Ово је за индексирање засновано на нули. И тако, родитељ са индексом 0 има своје лево дете на индексу 2×0+1=1 и десно дете на индексу 2×0+2=2. Родитељ на индексу 1 има своје лево дете на индексу 2×1+1=3 и десно дете на индексу 2×1+2=4; и тако даље.

По својству мин-хеап, родитељ на и је мањи или једнак левом детету на 2и+1 и мањи или једнак десном детету на 2и+2.

Гомила

Нагомилавање значи изградња гомиле. То значи преуредити елементе листе (или одговарајућег стабла) тако да задовољавају својство гомиле. На крају процеса хеапификације, листа или стабло је гомила.

Ако је претходна несортирана листа нагомилана, она ће постати:

Напомена: на листи има 12 елемената, а не 15. У другом реду су индекси. У процесу изградње гомиле, елементи су морали бити проверени, а неки замењени.

Приметите да је најмањи и први елемент 3. Остали елементи следе узлазно, али таласасто. Ако су лево и десно дете на позицијама 2и+1 и 2и+2 веће или једнако родитељу на и, онда је ово мин-гомила. Ово није потпуно наручивање или сортирање. Ово је делимично наручивање, према својству гомиле. Одавде почиње следећа фаза за сортирање гомиле.

Хеапифи временска сложеност

Временска сложеност је релативно време рада неког кода. Може се посматрати као број главних операција које тај код треба да заврши. Постоје различити алгоритми за изградњу гомиле. Најефикаснији и најбржи континуирано деле листу на два, проверавају елементе одоздо, а затим врше неку замену елемената. Нека је Н број практичних елемената у листи. Са овим алгоритмом, максимални број главних операција (замена) је Н. Временска сложеност за хеапифиинг је раније дата као:

Где је н Н и максимални могући број главних операција. Ова нотација се зове Биг-О нотација. Почиње са О великим словима, праћено заградама. Унутар заграда је израз за могући највећи број операција.

Запамтите: сабирање може постати множење ако се иста ствар која се додаје стално понавља.

Хеапсорт Иллустратион

Претходна несортирана листа ће се користити за илустрацију хеапсортирања. Наведена листа је:

Мин-хеап произведен са листе је:

Прва фаза у хеапсорт-у је производња гомиле која је произведена. Ово је делимично уређена листа. То није сортирана (потпуно сређена) листа.

Друга фаза се састоји од уклањања најмањег елемента, који је први елемент, из гомиле, поновног нагомилавања преостале гомиле и уклањања најмање елемената у резултатима. Најмањи елемент је увек први елемент у поново нагомиланој хрпи. Елементи се не уклањају и не бацају. Могу се послати у други низ редоследом којим се уклањају.

На крају, нови низ би имао све елементе сортиране (у потпуности), у растућем редоследу; а не више само делимично наређено.

У другој фази, прва ствар коју треба да урадите је да уклоните 3 и поставите га у нови низ. Резултати су:

и

Преостали елементи морају бити нагомилани пре него што се први елемент екстрахује. Гомила преосталих елемената може постати:

Екстраховање 5 и додавање на нову листу (низ) даје резултате:

и

Нагомилавање преосталог скупа би дало:

Екстраховање 6 и додавање на нову листу (низ) даје резултате:

и

Нагомилавање преосталог скупа би дало:

Издвајање 7 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа даје:

Екстраховање 9 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа даје:

Издвајање 11 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа би дало:

Издвајање 14 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа би дало:

Издвајање 15 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа би дало:

Издвајање 17 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа би дало:

Издвајање 19 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа даје:

Екстраховање 22 и додавање на нову листу даје резултате:

и

Нагомилавање преосталог скупа даје:

Екстраховање 24 и додавање на нову листу даје резултате:

и

Низ гомиле је сада празан. Сви елементи које је имао на почетку сада су у новом низу (листи) и сортирани.

Хеапсорт алгоритам

Иако је читалац можда прочитао у уџбеницима да се хеапсорт састоји од две фазе, хеапсорт се и даље може видети као да се састоји од једне фазе, која се итеративно смањује од датог низа. Уз то, алгоритам за сортирање помоћу хеапсорта је следећи:

• Нагомилајте несортирану листу.
• Извуците први елемент гомиле и ставите га као први елемент нове листе.
• Нагомилајте преосталу листу.
• Извуците први елемент нове гомиле и ставите као следећи елемент нове листе.
• Понављајте претходне кораке редом све док листа гомиле не буде празна. На крају, нова листа је сортирана.

Правилна сложеност времена Хеапсорта

Једностепени приступ се користи за одређивање временске сложености за хеапсорт. Претпоставимо да постоји 8 несортираних елемената које треба сортирати.

Максималан могући број операција је:

Просек ових бројева операција је:

Приметите да се последње четири гомиле на претходној илустрацији нису промениле када је први елемент уклоњен. Неке од претходних гомила се такође нису промениле када је први елемент уклоњен. При томе је бољи просечан број главних операција (замена) 3 а не 4,5. Дакле, бољи укупан просечан број главних операција је:

пошто лог _два 8 = 3.

Генерално, просечна сложеност времена случаја за хеапсорт је:

Где тачка означава множење, а н је Н, укупан број елемената у листи (било на листи).

Имајте на уму да је операција издвајања првог елемента занемарена. На тему временске сложености, занемарују се операције које трају релативно кратко време.

Кодирање у Ц++

У библиотеци алгоритама Ц++-а постоји функција маке_хеап(). Синтакса је:

Узима итератор који показује на први елемент вектора као свој први аргумент, а затим итератор који показује одмах иза краја вектора као свој последњи аргумент. За претходну несортирану листу, синтакса би се користила на следећи начин да би се добила минимална хрпа:

Овај код мења векторски садржај у минималну конфигурацију гомиле. У следећим Ц++ векторима, два вектора ће се користити уместо два низа.

Да бисте копирали и вратили први елемент вектора, користите векторску синтаксу:

Да бисте уклонили први елемент вектора и бацили га, користите векторску синтаксу:

Да бисте додали елемент на полеђини вектора (следећи елемент), користите векторску синтаксу:

Почетак програма је:

Укључене су библиотеке алгоритама и вектора. Следећа у програму је функција хеапсорт(), која је:

То је рекурзивна функција. Користи функцију маке_хеап() библиотеке Ц++ алгоритама. Други сегмент кода у дефиницији функције издваја први елемент из старог вектора након изградње гомиле и додаје као следећи елемент за нови вектор. Имајте на уму да су у дефиницији функције векторски параметри референце, док се функција позива са идентификаторима (именима).

Прикладна Ц++ главна функција за ово је:

Излаз је:

сортирано (потпуно).

Закључак

У чланку се детаљно говори о природи и функцији Хеап Сорт-а, обично познатог као Хеапсорт, као алгоритма за сортирање. Хеапифи Тиме Цомплекити, Хеапсорт илустрација и Хеапсорт као алгоритам су покривени и подржани примерима. Просечна временска сложеност за добро написан хеапсорт програм је О(нлог(н))