Какво е купчина?

Куча (heap) е специална дървовидна структура от данни, която удовлетворява свойството на кутията. Това свойство гласи, че за всяка върха, освен корена, стойността на ключа на тази върха трябва да бъде в определена връзка със стойността на ключа на нейния родител. Съществуват два основни типа кутии:

• Макс-купа (Max-heap): Стойността на ключа на всяка върха не е по-малка от стойността на ключовете на нейните деца. Максималният елемент се намира в корена.
• Мин-купа (Min-heap): Стойността на ключа на всяка върха не е по-голяма от стойността на ключовете на нейните деца. Минималният елемент се намира в корена.

Кутията обикновено се реализира като масив, което позволява ефективен достъп до елементите и изпълнение на операции. Връзката между родители и деца в масива е следната:

• За елемент с индекс i (започвайки от 0), левият му потомък е на индекс 2i + 1.
• Десният му потомък е на индекс 2i + 2.
• Родителят му е на индекс floor((i - 1) / 2).

Основните операции върху кутията:

• Insert (Вмъкване): Добавяне на нов елемент. Време за изпълнение O(log n), където n е броят на елементите.
• Extract-Max / Extract-Min: Премахване и връщане на максималния (в макс-купа) или минималния (в мин-купа) елемент. Време за изпълнение O(log n).
• Heapify (Изграждане на кутия): Преобразуване на произволен масив в кутия. Време за изпълнение O(n).

Кутиите се използват в алгоритми за сортиране (например, heapsort), в приоритетни опашки и в алгоритми за търсене на най-кратките пътища (например, алгоритъмът на Дейкстра).