Съдържание:
Определение - Какво означава Heap?
Купа, в контекста на структурата на данните, е структура на базата на дърво, която удовлетворява свойството heap, където на всеки елемент е присвоена ключова стойност или тегло. Ключът с по-ниска стойност винаги има родителски възел с ключ с по-висока стойност. Това се нарича структура на max-heap и сред всички възли коренният възел има най-високият ключ.
Понякога една дървовидна структура има правило за обърната структура, където елемент с ключ с по-висока стойност винаги има ключ с по-ниска стойност като родителски възел. Това се нарича структура на min-heap и сред всички възли коренният възел има най-ниския ключ.
Техопедия обяснява Хийп
Няма практически ограничения за броя на децата, които всеки възел може да има в една грамада, въпреки че всеки възел обикновено има най-много две. Купата се счита за най-ефективната реализация на абстрактния тип данни, известен като опашка с приоритет. Реализирането на купчината е от съществено значение в различни графични алгоритми (включително алгоритъма на Dijkstra), както и в алгоритъма за сортиране на купчини.
Heaps имат няколко варианта, които действат като абстрактни реализации с приоритет на типа данни с висока ефективност. Много приложения, като графични алгоритми, изискват реализиране на приоритетни опашки.
Масивът е най-често срещаната форма за изпълнение на купчината, при която не са необходими указатели за свързване между неговите елементи.
Heaps изпълняват множество операции, включително:
- Find-max: Търси за най-високия ключов възел сред група възли
- Find-min: Търси най-ниския ключов възел сред група възли
- Delete-max: Изтрива най-високия ключов възел сред група възли
- Изтрий-мин: Изтрива най-ниския ключов възел сред група възли
Heaps също включва функции, които извършват сливане, вмъкване и промени на клавишите.
Това определение е написано в контекста на структурата на данните
