Така че, ние постепенно се движи от малко или много прости до сложни, но ефективни методи. Пирамидално сортиране е първият от тези методи, изпълнението на който се оценява като О (п влизане п).
Като прелюдия към основен метод, нека разгледаме обърната опция вид. По време на преминаването, вместо да поставите най-малкия елемент в левия край на масива, ние ще изберем най-големият елемент, но е готов да се изгради последователност в десния край.
Пример действие за масива на [0]. на [7]:
Вертикална линия белязана от лявата граница вече е сортиран (вдясно) страна на масива.
Помислете за приблизителна оценка на броя на операциите в детайли.
Общо извършва п стъпки, всяка от които се състои от избиране на най-големия елемент от последователност на [0] .. на [I] и последващо обмен. Избор настъпва груба сила елементи в последователност, така че необходимото време за това: О (п). Така че, п стъпки за O (N) на всеки - това е O (N 2).
Ние направи подобрение: изграждане структура на данни, който позволява да се избере максималната елемент последователност не е О (п) и О (LOGN) време. Тогава общата ефективност е сортиране п * O (LOGN) = O (п влезте н).
Тази структура трябва също така да се даде възможност за бързо вмъкване на нови елементи (бързо да го изгради от оригиналния масив) и премахване на максималния елемент (той ще бъде поставен в една част на масива вече подредени - в десния край).
Така че, нека да се обади на пирамидата (Heap) двоично дърво на височина к, където
- всички възли имат дълбочина к или к-1 - балансирано дърво.
- където нивото на К-1 е изцяло запълнена, и нивата на к е изпълнен от ляво на дясно, т.е. пирамида форма има приблизително следния вид:
- тичане "пирамида собственост" на всеки елемент е по-малка или равна на родителя.
Как да се съхранява на пирамидата? Най-малко неприятен - да го постави в масив.
Съвместимост между геометрична структура като дърво и пирамида масив се определя, както следва:
- в [0] се съхранява дърво корен на
- ляво и дясно деца на елемента на [I] се съхраняват sootvetstvennno в [2i + 1] и [2i + 2]
Така масив, който съхранява пирамида следната характерна черта: а [Ь]> = а [2i + 1] и [Ь]> = на [2i + 2].
Предимства на този магазин пирамиди са очевидни:
- Няма допълнителни променливи само трябва да разберат веригата.
- възли се съхраняват от върха надолу, с по едно ниво.
- възли на едно ниво, се съхраняват в масива от ляво на дясно.
Пишем на пирамидата, показана по-горе като масив. От ляво на дясно, отгоре надолу: 94 67 18 44 55 12 06 42. Фигура място пирамида елемент в масива означен с десния върха му.
Възстановяване на пирамида от масива като геометричен обект лесно - свидетели верига на съхранение и изготвят като се излезе от корена.
Фаза 1 сортиране: изграждане на пирамида
Root пирамида конструкция може да бъде [к]. на [п], к = [размер / 2]. Тази част на масива отговаря пирамида собственост, тъй като не съществува индекси, Й: I = 2i + 1 (или J = 2i + 2). Просто защото тези, Й са извън границите на масива.
Трябва да се отбележи, че е погрешно да се каже, че [к] .. а [н] е пирамида като самостоятелен масив. Това е най-общо казано, не е вярно: тя може да бъде никакви елементи. Пирамида свойство се запазва само в рамките на източника, основният масив [0]. на [п].
След това, ние ще разшири част на масива като такава полезна функция, добавяне на един елемент на стъпка. Следващият елемент във всяка стъпка добавяне - този, който стои пред готовия част.
За добавяне на елемент задържа пирамидална, ние се използва следната процедура разширяване на пирамида [Ь + 1] .. на [п] за елемент на [Ь] наляво:
- Ние разглеждаме синове на ляво и дясно - в масива е [2i + 1] и [2i + 2] и да изберете най-голямото от тях.
- Ако тази позиция е повече от [в] - това се промени на [в] места и преминете към стъпка 2, позовавайки се на новата позиция на [в] в масива. В противен случай, на края на процедурата.
Нов елемент "проверени" през пирамидата.
Като се има предвид, че височината на пирамида ч <= log n, downheap требует O(log n) времени. Полный код процедуры построения пирамиды будет иметь вид:
По-долу са дадени за илюстрация на процеса на пирамидата 8 и елементи:
Геометричната тълкуването на ключовете от първоначалния сегмент на [размер / 2]. на [N] е листата в двоичен дърво, както е показано по-долу. Един по един останалите елементи се движат на мястото си, и така - докато цялата пирамида ще бъде построен.
Фигурата по-долу показва процеса на изграждане. Неподготвеност на пирамидата (в началото на масива) е боядисана в бял цвят, отговарящ края на имот пирамида на масива - в тъмното.
Фаза 2: действителното сортирането
Така че, задачата за изграждането на пирамидите в масива е успешно решен. Както може да се види от свойствата на пирамидата, на основния елемент винаги е максимална. Следователно фаза алгоритъм 2:
- Вземете горния член на пирамида [0]. на [п] (първи масив) и промяна от последната позиция. Сега "забрави" за този елемент и допълнително разглеждане на масив [0]. за [М-1]. За да го конвертирате в пирамидата нов първи елемент в достатъчна степен, за да се пресее.
- Повторете стъпка 1 до обработват част на масива се редуцира до един елемент.
Очевидно е, че в края на масива всеки път получава максималния елемент на текущия пирамидата, така че дясната страна постепенно се превръща в подредена последователност.
Код процедури външно сортиране:
Каква е работата на един алгоритъм?
Строителство пирамида отнема O (п влезте н) операции, както и дава по-точна оценка дори O (N) се дължи на факта, че действителното време на изпълнение downheap зависи от височината на пирамидата е вече установена.
Втората фаза отнема O (п влезте н) време: O (N) път, когато се взима максималният пресяване се случва и бившия последния елемент. Предимството на метода е стабилна: средният брой на хмел (п влизане п) / 2, и отклонение от тази стойност е относително малък.
Пирамидално сортиране използва повече памет.
Методът не е стабилна: масива в движение като "разклати", че първоначалната поръчка на елементите може да се променя на случаен принцип.
Неестествено поведение: частичен поръчване на масива не се взема предвид.
Свързани статии