Heap (Heap)

Heap-ը ծառի հատուկ կառուցվածք է, որը պահպանում է heap-ի հատկությունը:

Heap-երն ունեն երկու հիմնական տեսակ.

1. Max Heap: Ծնողական ուղещի արժեքը պետք է լինի մեծ կամ հավասար զավակ ուղещների արժեքներին:

2. Min Heap: Ծնողական ուղещի արժեքը պետք է լինի փոքր կամ հավասար զավակ ուղещների արժեքներին:

Մենք հիմնականում կենտրոնանալու ենք max-heap-ի վրա, քանի որ շատ գրադարաններում հնարավորությունների Waiting list (priority queue) իրականացման համար օգտագործվում է max-heap։ Max-heap-ի դեպքում ծառի արմատը ամենամեծ արժեքն է, իսկ տերևներն ունեն ամենափոքրերը։ Սակայն տերևային ուղещների միջև հատուկ լրացուցիչ կարգ չեք գտնի, հետևաբար երաշխավորված է միայն, որ արմատը կլինի ամենամեծ արժեքով ուղещը, իսկ նրա ամեն զավակ կլինի արմատի արժեքից ոչ մեծ:

Ուշադրություն դարձրեք, որ heap-ի վերջին տողը stets լրացվում է ձախից աջ։ Այսինքն՝ ձախակից տերևը լցվում է առաջինը, իսկ աջակից տերևը՝ ամենավերջինը, ինչպես երևում է նկարում:

Իրականացման խնդիրներ

Heap-ը կարող է իրագործվել (implementation) որպես զանգված, որտեղ զանգվածի առաջին տարրը heap-ի արմատն է։ Քանի որ յուրաքանչյուր ուղещ ունի ընդամենը 2 զավակ, ցուցակների վינדեքսավորումն ընդունում ենք այսպես.

1. Արմատն ունի Ինդեքս 1.

2. Ցանկացած ուղещի ձախ ու աջ զավակները գտնվում են համապատասխանաբար 2i և 2i+1 վանդակներում:

3. Ինդեքս 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:

Օրինակներ

Բացատրություն

Օրինակ 1

Օրինակ 2