Heap-ը ծառի հատուկ կառուցվածք է, որը պահպանում է heap-ի հատկությունը:
🗼
Եթե P-ն ծնողական ուղещ է C-ի համար, ապա P արժեքը պետք է լինի մեծ կամ հավասար (max-heap-ի դեպքում), կամ փոքր կամ հավասար (min-heap-ի դեպքում) C արժեքին:
Max-heap-ի օրինակ 8 ուղещներով
Heap-երն ունեն երկու հիմնական տեսակ.
Max Heap: Ծնողական ուղещի արժեքը պետք է լինի մեծ կամ հավասար զավակ ուղещների արժեքներին:
Min Heap: Ծնողական ուղещի արժեքը պետք է լինի փոքր կամ հավասար զավակ ուղещների արժեքներին:
Մենք հիմնականում կենտրոնանալու ենք max-heap-ի վրա, քանի որ շատ գրադարաններում հնարավորությունների Waiting list (priority queue) իրականացման համար օգտագործվում է max-heap։ Max-heap-ի դեպքում ծառի արմատը ամենամեծ արժեքն է, իսկ տերևներն ունեն ամենափոքրերը։ Սակայն տերևային ուղещների միջև հատուկ լրացուցիչ կարգ չեք գտնի, հետևաբար երաշխավորված է միայն, որ արմատը կլինի ամենամեծ արժեքով ուղещը, իսկ նրա ամեն զավակ կլինի արմատի արժեքից ոչ մեծ:
Ուշադրություն դարձրեք, որ heap-ի վերջին տողը stets լրացվում է ձախից աջ։ Այսինքն՝ ձախակից տերևը լցվում է առաջինը, իսկ աջակից տերևը՝ ամենավերջինը, ինչպես երևում է նկարում:
Իրականացման խնդիրներ
Heap-ը կարող է իրագործվել (implementation) որպես զանգված, որտեղ զանգվածի առաջին տարրը heap-ի արմատն է։ Քանի որ յուրաքանչյուր ուղещ ունի ընդամենը 2 զավակ, ցուցակների վינדեքսավորումն ընդունում ենք այսպես.
Արմատն ունի Ինդեքս 1.
Ցանկացած ուղещի ձախ ու աջ զավակները գտնվում են համապատասխանաբար 2i և 2i+1 վանդակներում:
Ինդեքս i-ում գտնվող ուղещի ծնողը գտնվում է i // 2-ում:
Վերը նշված heap-ը կարելի է գրի списъкում այսպես.
# Պարզապես կարդում ենք նկարի յուրաքանչյուր տողը և փոխանցում թվերը կողք կողքի
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# Կամ, ավելի հեշտ ընկալելու համար, նույնը տողատված
heap = [None, # Այլևս չենք օգտագործում [0]-րդ ինդեքսը, որպեսզի ցուցակավորումը պարզ լինի
8, # Ինդեքս [1]
5, 7, # Ինդեքսներ [2, 3]
1, 1, 6, 3, # Ինդեքսներ [4, 5, 6, 7]
1] # Ինդեքս [8]
Առաջադրանք: Ստուգել, արդյոք բինար ծառը heap է
Տրված է բինար ծառ, որը ներկայացված է n թիվ պարունակող զանգվածով (վերը նշված ինդեքսավորման սկզբունքով)։ Ձեզ խնդրում են գրել ծրագիր, որը ստանալով այդ թվերը, պետք է ստուգի՝ արդյոք ծառը պահպանում է max-heap-ի հատկությունը։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 100 000)։
Հաջորդ տողում տրված են n ողջ թվեր ( ), որոնք ներկայացնում են heap-ի տարրերը:
Ելք
Ծրագիրը ելքում պետք է տպի Yes, եթե մուտքագրված բինար ծառը պահպանում է max-heap-ի հատկությունը, հակառակ դեպքում — No:
Օրինակներ
Input
Output
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Բացատրություն
Օրինակ 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Օրինակ 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
