Gomila (struktura podataka)

Primer gomile

Gomila (binarna) je struktura podataka koju čine liste objekta koju možemo gledati kao na skoro kompletno binarno stablo. Svaki čvor u stablu odgovara rednom broju elemenata u listi. Svaki nivo stabla je potpuno popunjen izuzev najnižeg levog podstabla.Jer se elementi i stablo ubacuju sa leva na desne tj. prvo se popunjava levo podstablo, pa onda desno podstablo.

Roditelj mora biti veći ili jednaki od svog deteta.

Karakteristike gomile

Lista koja predstavlja gomilu je objekat koji ima dve osobine:

1. Dužinu (length) koja vraća broj elemenata u listi
2. Veličina gomile (heap-size) koja pokazuje koliko elemenata u nizu su sortirani u listi

Čvor u stablu je prvi element liste (i = 1) gde i označavamo kao indeks elemenata u listi. Levo dete dobijamo formulom 2*i. Desno dete dobijamo formulom 2*i+1.

Za sve elemente u gomili važi pravilo 0 <= A.heap-size <= A.length.

Operacije nad gomilom

Brisanje iz gomile

Funkcija koja omogućava brisanje elemenata iz gomile.

Ubacivanje u gomilu

Funkcija koja omogućava ubacivanje elemenata u gomilu.

Max-Heapify

Funkcija koja pravi da svaki čvor mora da svaki roditelj u stablu mora biti veći ili jednaki detetu.

Build-Max heap

Funkcija koja pravi ne rastuću gomilu od ne sortiranog niza.

Heap property

Je pravilo na kome je zasnovana gomila kao struktura podataka. I po ovom pravilu roditelj mora biti veći ili jednaki detetu.

Da bi smo održali

Složenost funkcija

Funkcija	Najbolji slučaj	Najgori slučaj
Build-Max heap	O(n)	O(n)
Max-Heapify	O(logn)	O(logn)
Ubacivanje u gomilu	O(logn)	O(logn)
Brisanje iz gomile	O(logn)	O(logn)
Naći min	O(1)	O(1)
Naći maks	O(1)	O(1)

Održavanje Max heap property

Da bi smo mogli da održavamo Max heap property, mi moramo da pozivamo funkciju Max-Heapify. Funkciji prosleđujemo listu i indeks elemenata koji se nalazi u listi. Kada se poziva Max-Heapify za određeni čvor, funkcija pretpostavlja da su levi i desni list čvora Max-Heap, ali i da njihov roditelj može biti malji od svoje dece. I ovo krši pravilo max heap property. Ako se ovo desi Max-Heapify omogićava da roditelj u stablu zameni mesto i indeks sa najvećim detetom. Posto smo zamenili roditelja sa detetom, sad moramo da proverimo da li narušavamo heap property i tom (levom ili desnom) podstablu sad rekurzivno pozivamo funkciju Max-Heapify u tom podstablu da bi smo održavali Max heap property.

Pseudo kod

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)

Napraviti gomilu

Koristimo proceduru Max-Heapify da bi smo od liste dužine n napravili max-neap. Procedura Build-Max heap prolazi kroz sve čvorove stabla i za svaki čvor poziva funkciju Max-Heapify.

Pseudo kod

Build-Max heap(А)

A.heap-size = A.length

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

Max-Heapify(A, i)

Vrste gomila

Imamo dve vrste gomila max-heaps i min-heaps. I u oba slučaja mora biti zadovoljen Heap property. Samo sto kod max-heap roditelj je veći ili jednak detetu. I kod max-heap najveći čvor je na vrhu stabla. A kod min-heap roditelj je manji ili jednak detetu. I najmanji čvor je na samom vrhu stabla.

Algoritam za sortiranje

Primer hipsort algoritma. Prosečna složenost: $O(n{\text{ }}\log {\text{ }}n)$ Najgora složenost:
$O(n^{2})$ Prostorna složenost: $O(1)$

Algoritam za sortiranje gomila zove se Heap Sort i njegova složenost je O(nlogn).

Pseudo kod

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)

Literatura

• Cormen, Thomas H. (1990 (first edition)). „Heapsort”. Introduction to Algorithms, Third Edition (PDF) (na jeziku: engleski). Charles E. Leiserson Ronald L. Rivest Clifford Stein (3. izd.). United States: MIT Press. str. 1292. ISBN 978-0-262-03384-8. Arhivirano iz originala (PDF) 18. 10. 2016. g. Pristupljeno 03. 01. 2016. „Heap(Gomila)” 
• Škarić, Milan. „12”. Uvod u programiranje (na jeziku: Srpski jezik). Beograd: Mikro knjiga. „Binarno stablo” CS1 održavanje: Neprepoznat jezik (veza)
• Introductions to algorithms -Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, knjigu možete pogledati ovde Arhivirano na sajtu Wayback Machine (18. oktobar 2016)
• Algoritmi i strukture podataka - Milo Tomašević