Алгоритъмсортиране на купчина (HeapSort) - Studiopedia
В някои приложения (например при проблеми с управлението на оборудването в реално време) е изключително важно да има гаранция, че времето за изпълнение на критични програмни клонове, дори и в най-лошия случай, няма да надвиши определена определена стойност. За такива задачи използването на QuickSort може да е неприемливо поради недостатъка на този алгоритъм, споменат по-горе - времето за работа от порядъка на O(n 2 ) в най-лошия случай. В тази ситуация трябва да използвате алгоритъм, който гарантирано ще бъде бърз дори и в най-лошия случай.
Най-известният от тези алгоритми е HeapSort, което на български се нарича heapsort.
Алгоритъмът се основава на концепцията за пирамида.
Масив A се нарича пирамида, ако за всички негови елементи са валидни следните неравенства:
(3.1)
Значението на неравенствата (3.1) може да бъде ясно илюстрирано на фиг. 3.1.
Ориз. 3.1. Представяне на пирамида под формата на дърво
На фигурата пирамида от 10 елемента е изобразена като балансирано двоично дърво, чиито върхове са номерирани отгоре надолу и отляво надясно. В този случай елементът ak винаги ще бъде "баща" на елементите a2k и a2k+1 в дървото (ако такива елементи съществуват). Тогава неравенствата (3.1) означават, че стойността на "бащата" трябва да бъде не по-малка от стойностите на всеки от "синовете".
Трябва обаче да се помни, че пирамидата не е дърво, а масив с определени свойства и изображението на пирамидата под формата на дърво е дадено само за яснота.
Пирамидата не е непременно сортиран масив, но служи като удобен междинен резултат при сортиране. Имайте предвид, че първият елемент на пирамидата (a1) винаги е максималният елемент на масива.
работаАлгоритъмът HeapSort се състои от две последователни фази. В първата фаза оригиналният масив се изгражда отново в пирамида, а във втората фаза от пирамидата се изгражда сортиран масив.
Основната операция, използвана както в първата, така и във втората фаза на сортиране, е така нареченото пресяване на елемент през пирамидата.
Да приемем, че неравенствата (3.1) са изпълнени за елементите на пирамидата, започвайки от индекса k+1 (т.е. за елементите ak+1, ak+2, … , an). Процедурата за пресяване на елемента ak трябва да гарантира, че (3.1) е в сила за ak и не нарушава тези неравенства за ak+1, ak+2, … , an.
Алгоритъмът за пресяване е както следва.
1. Ако ak няма синове (т.е. 2k > n), тогава пресяването е приключило.
2. Ако ak има точно един син (т.е. 2k = n), тогава присвоете l := n и отидете на стъпка 4.
3. Сравнете стойностите на двамата сина на ak: ако a2k > a2k+1, тогава l := 2k, в противен случай l := 2k + 1 (т.е. l е индексът на най-големия от синовете на ak).
4. Сравнете стойностите на елемент ak със стойността на неговия по-голям син al: ако ak
4. Ако n>gt; 1, след това преминете към стъпка 1, в противен случай сортирането е завършено.
При всяка итерация на втората фаза максимумът от елементите, останали в нея, се изключва от пирамидата. Този елемент се записва на правилното му място в сортирания масив. В края на алгоритъма цялата пирамида се превръща в сортиран масив.
Нека оценим времето за изпълнение на всяка фаза на алгоритъма HeapSort. Първата фаза се състои от n/2 операции за пресяване, всяка от които включва най-много log2(n) итерации на цикъла. От тук можем лесно да получим оценката Tmax(n) = O(n×log(n)) за първата фаза. Тази оценка обаче е твърде груба. В бъдеще ще се нуждаем от по-точна оценка на времето за изпълнение на първата фаза на HeapSort. Придобивамтакава оценка, разгледайте фиг. 3.2.
Ориз. 3.2. Брой итерации на пресяване при изграждане на пирамида
От всички n елемента на масив A, около половината (n/2) нямат синове и не изискват пресяване (т.е. броят на повторенията на пресяване е 0). Една четвърт от елементите (n/4) имат синове, но не и внуци, за тези елементи не може да се извърши повече от една итерация на пресяване. За една осма от елементите (n/8) могат да бъдат извършени две итерации, за една шестнадесета (n/16) три итерации и т.н. Общият брой итерации на пресяване се определя по формулата: n (0×1/2 + 1×1/4 + 2×1/8 + 3×1/16 + …). Разтърсвайки спомени за математическия анализ, можете да изчислите стойността на сумата от серията в скоби; тази стойност е равна на 1. Така получаваме линейна оценка на времето за първата фаза: Tmax(n) = O(n).
Втората фаза на алгоритъма е основно пресяване през свиващата се пирамида. Броят на повторенията на цикъла може грубо да се изчисли като сумата от log2(n) + log2(n–1) + log2(n–2) + … + log2(3) + log2(3). Вярваме без доказателство, че до O-голяма тази сума дава Tmax(n) = O(n×log(n)).
Времето на работа на алгоритъма като цяло се определя от по-отнемащата време втора фаза и удовлетворява оценката Tmax(n) = O(n×log(n)). Може да се докаже, че същата оценка е валидна и за средното време за сортиране: Tav(n) = O(n×log(n)). По този начин HeapSort е алгоритъм за сортиране, който гарантира доста бърза работа дори в случай на най-нещастните първоначални данни. Това отличава HeapSort от QuickSort, който не предоставя такава гаранция. От друга страна, практиката показва, че средно алгоритъмът HeapSort е около два пъти по-бавен от QuickSort.
Не намерихте това, което търсихте? Използвайте търсачката: