Ի՞նչ է տոպրակը (տվյալների կառուցվածքների համատեքստում)։

Հավաք (heap) — դա մասնագիտացված ծառ է, որը օգտագործվում է որպես տվյալների կառուցվածք: Հավաքի հիմնական հատկությունը՝ մասնակի կարգավորվածություն է. ցանկացած հանգույցի համար կատարվում է պայման, որ ծնողի արժեքը մեծ կամ հավասար է նրա ցանկացած երեխայի արժեքին (max-heap) կամ փոքր կամ հավասար (min-heap):

Հիմնական հատկանիշներ՝

• Բինար ծառ: Ամենից հաճախ այն իրականացվում է որպես բինար ծառ, որտեղ յուրաքանչյուր հանգույցի առավելագույնը երկու զավակ կա:
• Լրիվ բինար ծառ: Բոլոր մակարդակներում, բացի հնարավոր վերջինից, ծառը լրիվ է: Վերջին մակարդակի հանգույցները լրացվում են ձախից աջ: Սա թույլ է տալիս արդյունավետ պահել հավաքը որպես զանգված:
• Հավաքի հատկություն:
  • Max-heap: Յուրաքանչյուր հանգույցի արժեքը մեծ կամ հավասար է նրա զավակների արժեքներին: Ամենամեծ տարրն ամենից վերևում է:
  • Min-heap: Յուրաքանչյուր հանգույցի արժեքը փոքր կամ հավասար է նրա զավակների արժեքներին: Ամենափոքր տարրն ամենից վերևում է:

Հավաքի հիմնական գործողությունները՝

• Էլեմենտի ավելացում: Նոր տարր ավելացնելը և պահպանել հավաքի հատկությունը:
• Էլեմենտի հեռացում: Հավաքի վերևի տարրին (ամենամեծ կամ ամենափոքր՝ կախված հավաքի տեսակից) հեռացնելը և պահպանել հավաքի հատկությունը:
• Հավաքի ստեղծում: Հավաքի կառուցում զանգվածից:

Հավաքի կիրառումները՝

• Տեսակավորում: Հիփ-սորտինգ ալգորիթմ:
• Առաջնահերթության հերթեր: Էֆեկտիվ իրականացում, որտեղ տարրերը մշակվում են առաջնահերթության կարգով:
• Որոնման ալգորիթմներ: Օրինակ՝ k-րդ մեծ տարրն որոնելը:
• Գրաֆային ալգորիթմներ: Օրինակ՝ Դեյքստրայի ալգորիթմ:

Հավաքի ներկայացում զանգվածով:

Քանի որ հավաքը հանդիսանում է լրիվ բինար ծառ, այն կարող է արդյունավետորեն պահվել զանգվածում առանց ցուցիչների:

• Եթե հանգույցը գտնվում է i ինդեքսում, նրա ձախ զավակը գտնվում է 2*i + 1 ինդեքսում:
• Նրա աջ զավակը գտնվում է 2*i + 2 ինդեքսում:
• Նրա ծնողը գտնվում է (i - 1) / 2 ինդեքսում:

# Min-heap ներկայացման օրինակ զանգվածում
heap_array = [10, 15, 20, 17, 25, 30]

# Մարմինը: heap_array[0] = 10
# Ձախ զավակը: heap_array[2*0 + 1] = heap_array[1] = 15
# Աջ զավակը: heap_array[2*0 + 2] = heap_array[2] = 20
# Ծնողը ինդեքսի 3 (17): heap_array[(3-1)//2] = heap_array[1] = 15