Лабораторная работа № 2

Тема. Бинарные кучи.

Цель:

-         изучить устройство и принцип заполнения бинарных куч

-         научиться использовать на практике основные алгоритмы по обработке бинарных куч

Теоретическая часть

Полным бинарным деревом называется такое дерево, в котором каждая вершина имеет не более двух «сыновей», а заполнение вершин осуществляется в порядке от верхних уровней к нижним, причем на одном уровне заполнение вершин производится слева направо.

Количество вершин в полном бинарном дереве высоты h может изменяться от2_­^h (минимум) до 2_­^h+1-1 (максимум).

Полное бинарное дерево с К вершинами удобно реализуется с помощью простого массива. Для этого необходимо представить, что у элемента с индексом iсыновьями являются элементы с индексами 2i и 2i + 1, причем 2i ≤ K и 2i + 1≤ K.

Вполне очевидно, что «отцом» вершины с индексом j является вершина с индексом , но следует помнить, что у корневой вершины «отца» нет.

Кроме массива удобно хранить еще одну переменную, которая определяет количество вершин в дереве. Пусть это будет переменная Num.

Основным свойством (инвариантом) структуры данных куча является условие, что элементы в ней организованы таким образом, что приоритет любой вершины не ниже приоритета каждого из ее «сыновей».

Так если в качестве приоритета рассматривать время, которое элемент может «ожидать», то приоритет вершины будет тем выше, чем меньше время возможного ожидания.

Бинарная куча – это полное бинарное дерево, для которого выполняется основное свойство структуры данных куча.

Это свойство требует выполнения условия, что для любой тройки элементов с индексами i, 2i, 2i + 1 элемент с индексом i должен иметь максимальный приоритет (т.е. в куче из трех элементов более сильный всегда сверху).

Ход работы

1.      Разработайте программу в соответствии со следующими требованиями:

а)      создание бинарной кучи (случайное / ручной ввод);

б)      добавление элемента в бинарную кучу;

в)      удаление элемента из бинарной кучи;

г)       все операции должны быть наглядно представлены.

Важно: обязательно соблюдение инварианта!

2.      Напишите отчет, содержащий исходные тексты программ.