Абстрактные кучи

Сентябрь 7, 2022

Главная
Алгебра
Абстрактные кучи

Содержание

2. Определение кучи Куча – это абстрактный тип данных, очень похожий на бинарное дерево поиска, но отличающийся
3. Определение кучи Куча – это полное бинарное дерево, обладающее следующими свойствами: она пуста или Ключ, содержащийся
4. Операции над абстрактной кучей MAKE NULL(Н) – делает кучу Н пустой; EMPTY(Н) – определяет, пуста ли
5. Реализация кучи в виде массива Реализация кучи в виде массива содержит : Массив элементов кучи; Счетчик(количество
6. Удаление элемента из кучи
7. Алгоритм удаления элемента из кучи Находим элемент, содержащий наибольший поисковый ключ(корень дерева); Удаляем этот элемент получаем
8. Вставка элемента в кучу Вставляем узел 15 Элемент просачивается наверх Элемент просачивается наверх
10. Скачать презентацию

Слайд 2

Определение кучи
Куча – это абстрактный тип данных, очень похожий на бинарное

дерево поиска, но отличающийся от него двумя важными свойствами:
Бинарное дерево поиска считается упорядоченным, а порядок элементов в куче имеет совершенно другой смысл.
Бинарное дерево поиска может иметь разную форму, а кучи всегда являются совершенными бинарными деревьями.

Слайд 3

Определение кучи
Куча – это полное бинарное дерево, обладающее следующими свойствами:
она

пуста
или
Ключ, содержащийся в ее корне, больше ключу каждого его дочернего узла и
поддеревья корня являются кучами.
Куча называется максимальной, если корень содержит элемент, имеющий наибольший ключ поиска.
Куча называется минимальной, если корень содержит элемент, имеющий наименьший ключ поиска.

Слайд 4

Операции над абстрактной кучей
MAKE NULL(Н) – делает кучу Н пустой;
EMPTY(Н) –

определяет, пуста ли куча;
INSERT (x,Н) – вставляет элемент х в кучу Н;
DELETE (х,Н) – извлекает, а затем удаляет элемент х из корня кучи Н

Слайд 5

Реализация кучи в виде массива
Реализация кучи в виде массива содержит :
Массив

элементов кучи;
Счетчик(количество элементов, содержащихся в куче).

0
1
2
3
4
5

Слайд 6

Удаление элемента из кучи

Слайд 7

Алгоритм удаления элемента из кучи
Находим элемент, содержащий наибольший поисковый ключ(корень дерева);
Удаляем

этот элемент получаем две разъединенные кучи;
Объединяем оставшиеся узлы в новую кучу:
Помещаем последний узел дерева в корень
Получаем полукучу (кучу, в которой элемент, находящийся в корне кучи, находится не на своем месте);
Находим наибольший дочерний узел(дочерний узел с наибольшим ключом);
Меняем местами эти узлы.

Слайд 8