Гомила (структура података)

Гомила (бинарна) је структура података коју чине листе објекта коју можемо гледати као на скоро комплетно бинарно стабло.^[1] Сваки чвор у стаблу одговара редном броју елемената у листи. Сваки ниво стабла је потпуно попуњен изузев најнижег левог подстабла.Јер се елементи и стабло убацују са лева на десне тј. прво се попуњава лево подстабло, па онда десно подстабло.

Родитељ мора бити већи или једнаки од свог детета.

Карактеристике гомиле

Листа која представља гомилу је објекат који има две особине:

Дужину (length) која враћа број елемената у листи
Величина гомиле (heap-size) koja показује колико елемената у низу су сортирани у листи

Чвор у стаблу је први елемент листе (и = 1) где и означавамо као индекс елемената у листи. Лево дете добијамо формулом 2*и. Десно дете добијамо формулом 2*и+1.

За све елементе у гомили важи правило 0 <= A.heap-size <= A.length.^[2]

Операције над гомилом

Брисање из гомиле

Функција која омогућава брисање елемената из гомиле.

Убациванје у гомилу

Функција која омогућава убацивање елемената у гомилу.

Max-Heapify

Функција која прави да сваки чвор мора да сваки родитељ у стаблу мора бити већи или једнаки детету.

Build-Max heap

Функција која прави не растућу гомилу од не сортираног низа.

Heap property

Је правило на коме је заснована гомила као структура података. И по овом правилу родитељ мора бити већи или једнаки детету.

Да би смо одржали

Сложеност функција

Функција	Најбољи случај	Најгори случај
Build-Max heap	О(n)	О(n)
Max-Heapify	О(logn)	О(logn)
Убациванје у гомилу	О(logn)	О(logn)
Брисање из гомиле	О(logn)	О(logn)
Наћи мин	О(1)	О(1)
Наћи макс	О(1)	О(1)

Одржавање Max heap property

Да би смо могли да одржавамо Max heap property, ми морамо да позивамо функцију Max-Heapify. Функцији прослеђујемо листу и индекс елемената који се налази у листи. Када се позива Max-Heapify за одређени чвор, функција претпоставља да су леви и десни лист чвора Max-Heap, али и да њихов родитељ може бити маљи од своје деце. И ово крши правило маx heap property. Ако се ово деси Max-Heapify омогићава да родитељ у стаблу замени место и индекс са највећим дететом. Посто смо заменили родитеља са дететом, сад морамо да проверимо да ли нарушавамо heap property и том (левом или десном) подстаблу сад рекурзивно позивамо функцију Max-Heapify у том подстаблу да би смо одржавали Max heap property.

Псеудо код

Max-Heapify(A, i)

l=Left(i)

r=Right(i)

if l <=A.heap-size and A[l]>A[i]

largest = l

else largest = i

if r<=A.heap-size and A[r]>A[largest]

largest = r

if largest ≠ i

excange A[i] with largest

Max-Heapify(A, largest)

Направити гомилу

Користимо процедуру Max-Heapify да би смо од листе дужине n направили маx-неаp. Процедура Build-Max heap пролази кроз све чворове стабла и за сваки чвор позива функцију Max-Heapify.

Псеудо код

Build-Max heap(А)

A.heap-size = A.length

for i = [A.length/2] downto 1

Max-Heapify(A, i)

Врсте гомила

Имамо две врсте гомила max-heaps и min-heaps. И у оба случаја мора бити задовољен Heap property. Само сто код max-heap родитељ је већи или једнак детету. И код max-heap највећи чвор је на врху стабла. А код min-heap родитељ је мањи или једнак детету. И најмањи чвор је на самом врху стабла.

Алгоритам за сортирање

Пример hipsort алгоритма. **Просечна сложеност**: $O(n{\text{ }}\log {\text{ }}n)$ **Најгора сложеност**:
$O(n^{2})$ **Prostorna složenost**: $O(1)$

Алгоритам за сортирање гомила зове се Heap Sort и његова сложеност је О(nlogn).

Псеудо код

BuildMax-Heap(A)

for i = A.length downto 2

exchange A[1] with A[i]

A.heap-size = A.heap-size-1

MAX-HEAPIFY(A,1)

Референце

^ Шкарић, Милан. „12”. Увод у програмирање (на језику: Српски језик). Београд: Микро књига. „Бинарно стабло”
^ Cormen, Thomas H. (1990 (first edition)). „Heapsort”. Introduction to Algorithms, Third Edition (PDF) (на језику: енглески). Charles E. Leiserson Ronald L. Rivest Clifford Stein (3. изд.). United States: MIT Press. стр. 1292. ISBN 978-0-262-03384-8. Архивирано из оригинала (PDF) 18. 10. 2016. г. Приступљено 08. 2. 2016. „Heap(Гомила)” Проверите вредност парамет(а)ра за датум: |date= (помоћ)

Литература

Cormen, Thomas H. (1990 (first edition)). „Heapsort”. Introduction to Algorithms, Third Edition (PDF) (на језику: енглески). Charles E. Leiserson Ronald L. Rivest Clifford Stein (3. изд.). United States: MIT Press. стр. 1292. ISBN 978-0-262-03384-8. Архивирано из оригинала (PDF) 18. 10. 2016. г. Приступљено 03. 01. 2016. „Heap(Гомила)” Проверите вредност парамет(а)ра за датум: |date= (помоћ)
Шкарић, Милан. „12”. Увод у програмирање (на језику: Српски језик). Београд: Микро књига. „Бинарно стабло”
Introductions to algorithms -Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
Алгоритми и структуре података - Мило Томашевић

[Стабло-1] Шкарић, Милан. „12”. Увод у програмирање (на језику: Српски језик). Београд: Микро књига. „Бинарно стабло”

[Heap-2] Cormen, Thomas H. (1990 (first edition)). „Heapsort”. Introduction to Algorithms, Third Edition (PDF) (на језику: енглески). Charles E. Leiserson Ronald L. Rivest Clifford Stein (3. изд.). United States: MIT Press. стр. 1292. ISBN 978-0-262-03384-8. Архивирано из оригинала (PDF) 18. 10. 2016. г. Приступљено 08. 2. 2016. „Heap(Гомила)” Проверите вредност парамет(а)ра за датум: |date= (помоћ)

[1]

[2]