Овоолго(Heap)-ын Эрэмбэлэлт
Дарааллын элементүүд тусгайлсан түлхүүртэй, тэр түлхүүрийн утгаар дарааллын элементүүд байршдаг бол түүнийг эрэмбэтэй дараалал гэж нэрлэдэг. Түлхүүрийн утгаар ийм дарааллыг минимум ба максимум эрэмбэтэй дараалал гэж хуваадаг. Эрэмбэтэй дарааллаас элементийг дарааллын оройгоос авдаг. Шинэ элемент нэмэхдээ ч оройгоос доош гүйлгэж зохих байрыг нь хайж олдог. Эрэмбэтэй дарааллын сонгодог жишээ бол Heap буюу Овоолго юм.
Овоолгыг хэрэгжүүлэхдээ max эрэмбэтэй дараалыг ашиглана. Эхлээд дарааллын элементүүдийг агуулсан массивыг дээр овоолгын шинж чанартай (heapify үйлдэл) болгоход O(n) хугацаа шаардана. Тоон дарааллыг буурахаар эрэмбэлэхдээ овоолгыг хоосон болтол нь овоолгын орой дээр байгаа хамгийн их утгатай элементийг овоолгоос гарган авч шинэ дараалалд нэмэх замаар гүйцэтгэнэ.
Овоолгын өндөр
Нэгэнт овоолго нь гүйцэд хоёртын мод болохоор n зангилаатай овоолгын өндөр log2(n+1).
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
