Ի՞նչ է հոտը։

Հեյպ (heap) — դա հատուկ ծառային կառուցվածք է, որը բավարարում է հեյպի հատկությանը: Այս հատկությունը նշում է, որ ցանկացած հանգույցի համար, բացի արմատից, այդ հանգույցի բանալի արժեքը պետք է լինի որոշ հարաբերության մեջ իր ծնողի արժեքի հետ: Կան երկու հիմնական հեյպի տեսակներ՝

• Max-հեյպ (Max-heap): Յուրաքանչյուր հանգույցի բանալի արժեքը չի պակասում իր երեխաների բանալի արժեքներից: Ամենամեծ տարրն գտնվում է արմատում:

• Min-հեյպ (Min-heap): Յուրաքանչյուր հանգույցի բանալի արժեքը չի գերազանցում իր երեխաների բանալի արժեքները: Ամենափոքր տարրն գտնվում է արմատում:

Հեյպը սովորաբար իրականացվում է որպես զանգված, ինչը թույլ է տալիս արդյունավետ մուտք գործել տարրեր և կատարել գործողություններ: Զանգվածում ծնողի և երեխաների միջև կապը հետևյալն է.

• i ինդեքսով տարրին (սկսած 0-ից), նրա ձախ զավակը գտնվում է 2i + 1 ինդեքսում:

• Նրա աջ զավակը 2i + 2 ինդեքսում:

• Նրա ծնողը floor((i - 1) / 2) ինդեքսում:

Հիմնական գործողություններ հեյպի վրա:

• Insert (Ավելացնել): Նոր տարր ավելացնել: Վերջացումն ժամանակը O(log n), որտեղ n տարրերի քանակն է:

• Extract-Max / Extract-Min: Հեռացնել և վերադարձնել առավելագույնը (max-hayp-ում) կամ նվազագույնը (min-hayp-ում) տարր: Վերջացումն ժամանակը O(log n):

• Heapify (Հեյպի կառուցում): Յուրաքանչյուր զանգվածից հեյպ ստեղծել: Վերջացումն ժամանակը O(n):

Հեյպները օգտագործվում են դասակարգման ալգորիթմներում (օրինակ, heapsort), առաջնահերթության հերթերում և կարճ ճանապարհների որոնման ալգորիթմներում (օրինակ, Dijkstra-ի ալգորիթմ):