Jump to content

Овоолго

Википедиа — Чөлөөт нэвтэрхий толь
 Дарааллын элементүүд тусгайлсан түлхүүртэй, тэр түлхүүрийн утгаар дарааллын элементүүд байршдаг бол түүнийг эрэмбэтэй дараалал гэж нэрлэдэг. Түлхүүрийн утгаар ийм дарааллыг минимум ба максимум эрэмбэтэй дараалал гэж хуваадаг. Эрэмбэтэй дарааллаас элементийг дарааллын оройгоос авдаг. Шинэ элемент нэмэхдээ ч оройгоос доош гүйлгэж зохих байрыг нь хайж олдог. Эрэмбэтэй дарааллын сонгодог жишээ бол Heap буюу Овоолго юм.


Овоолго(Heap)-ын Эрэмбэлэлт

Овоолгыг хэрэгжүүлэхдээ max эрэмбэтэй дараалыг ашиглана. Эхлээд дарааллын элементүүдийг агуулсан массивыг дээр овоолгын шинж чанартай (heapify үйлдэл) болгоход O(n) хугацаа шаардана. Тоон дарааллыг буурахаар эрэмбэлэхдээ овоолгыг хоосон болтол нь овоолгын орой дээр байгаа хамгийн их утгатай элементийг овоолгоос гарган авч шинэ дараалалд нэмэх замаар гүйцэтгэнэ.

Овоолгын өндөр

Нэгэнт овоолго нь гүйцэд хоёртын мод болохоор n зангилаатай овоолгын өндөр log2(n+1).