Какво е стек (в контекста на структури от данни)?

Куча (heap) е специализиран дърво, което се използва като структура от данни. Основното свойство на кучата е частично подреждане: за всеки връх, условието е, че стойността на родителския връх е по-голяма или равна на стойността на който и да е от неговите деца (max-heap) или по-малка или равна (min-heap).

Ключови характеристики:

• Бинарно дърво: Обикновено се реализира като бинарно дърво, където всеки възел има най-много две деца.
• Пълно бинарно дърво: На всички нива, освен може би последното, дървото е напълно запълнено. Възлите на последното ниво се запълват отляво надясно. Това позволява ефективно съхраняване на кучата като масив.
• Свойство на кучето:
  • Max-heap: Стойността на всеки възел е по-голяма или равна на стойностите на неговите деца. Максималният елемент винаги е в корена.
  • Min-heap: Стойността на всеки възел е по-малка или равна на стойностите на неговите деца. Минималният елемент винаги е в корена.

Основни операции с кучето:

• Добавяне на елемент: Добавяне на нов елемент и поддържане на свойството на кучето.
• Премахване на елемент: Премахване на кореновия елемент (максималния или минималния в зависимост от типа на кучето) и поддържане на свойството на кучето.
• Създаване на куче: Изграждане на куче от масив от елементи.

Приложения на кучето:

• Сортиране: Алгоритъм за сортиране чрез купа (Heapsort).
• Очереди с приоритет: Ефективна реализация на опашки, където елементите се обработват по ред на приоритет.
• Алгоритми за търсене: Например, търсене на 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