Search This Blog

2010-05-25

Heap sort (Heap эрэмбэлэлт)

Бүтэц үзэж буй, мөн бүтэц сонирхон судлаж байгаа оюунлаг залуучууддаа зориулан санаа авч болмоор хэдэн зүйл оруулъя.
Heap sort:
Heap sort -н ажиллах хуагцаа: n*log(n).
Энд n эрэмбэлэх өгөгдлийн тоо. 

Heap sort-н бүх орой өөрийн хүүхдүүдээс их байх ёстой. Тиймээс орой бүрийн хувьд хүүхдүүдтэй нь харьцуулалт хийж, хэрэв аль нэг нь их байвал тэр хүүг эцэг оройтой нь солино.

 Энэ зурган дээр харагдаж байгаачлан 16 нь 26с бага учраас 26г 16тай солин 26 нь эцэг болно.
Энэ мэтчилэн бүх эцгийн хувьд шалгалт хийн, хэрэв эцгээсээ их утгатай хүү олдвол тухайн хүүг эцэгтэй нь сольж явсаар MAX heap үүсгэх юм.

Мах heap үүссэний дараа үндсэн (root) оройг хамгийн сүүлийн оройгоор солино. Харин үндсэн оройгоо буцаан модонд оруулж болохгүй. Тиймээс ямар нэг хүснэгтэнд хадгалж болох юм.
Одоо үндсэн орой маань хамгийн их нь байхаа больсон учраас эхний алхамруу шилжин ахин heap мод үүсгэх хэрэгтэй.  Мод хоосрох хүртэл энэ алхамуудыг давтах ба мод хоосрох үед өгөгдөл маань эрэмбэлэгдэж дууссан байх юм.

Мод ашиглан heap sort- г хэрэгжүүлэх нь яршиг төвөг ихтэй юм. Тиймээс хүснэгт ашиглан амархан аргаар шийдэж болно.


Модыг хүснэгт рүү шилжүүлэхэд зурган дээр харагдаж байгаачлан хамгийн эхний нүдэнд модны орой (root) байрлах юм.
Харин дараа дараагийн нүдэн хүүхдүүд нь байна
i -г хүснэгтийн индекс гэвэл орой болгоны хувьд өөрийн зүүн хүүрүү: 2i + 1; харин баруун хүүрүү: 2i +2 томъёогоор хандах юм.
Ингээд хүснэгт ашиглаж хийсэн бичкээн heap sort ийг орууллаа.

Хэрвээ код нь хэрэгтэй бол санал сэтгэгдлээ үлдээгээрэй. :D





Зургуудыг эндээс авлаа.
Илүү дэлгэрэнгүй мэдэхийг хүсвэл тэр тухайгаа мэдэгдээрэй залуусаа.
Ойлгомжгүй, эсвэл буруу тайлбарласан зүйл байвал залруулж өгнө үү.

No comments:

Зурхай