Гомила (структура података)
Гомила (бинарна) је структура података коју чине листе објекта коју можемо гледати као на скоро комплетно бинарно стабло.[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 родитељ је мањи или једнак детету. И најмањи чвор је на самом врху стабла.
Алгоритам за сортирање
Prostorna složenost:
Алгоритам за сортирање гомила зове се 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)
Референце
Литература
- Шаблон:Cite book
- Шаблон:Cite book
- Introductions to algorithms -Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, књигу можете погледати овде Шаблон:Wayback
- Алгоритми и структуре података - Мило Томашевић