Куча (структура данных).

Имеется список целых чисел 5, 1, 7, 3, 9, 2, 8. Построим два дерева, в которых каждому узлу соответствует одно из значений этого списка, причем первое дерево будет организованно нисходящей иерархией, а второе – восходящей.

Два получившихся дерева полностью удовлетворяют свойству кучи: если Nявляется узлом-предком относительно M, а M соответственно узлом-потомком узла N, то для max-кучи всегда выполняется неравенство NM, а для min-кучи NM.

Когда корневой элемент кучи имеет наибольшее из возможных значений, то ее называют max-кучей, а когда наименьшее – min-кучей.

Данные, представленные такой структурой, удобны в обработке; некоторые операции с ними весьма не ресурсоемки, например, удаление минимального (для min-кучи) или максимального (для max-кучи) элемента, добавление нового элемента и др.

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

Пусть известно, с каким из видов дерева (min- или max-кучей) имеем дело. Тогда определить максимальный элемент max-кучи, и минимальный элемент min-кучи не составит труда, поскольку в обоих случаях это элемент под одним и тем же номером, а именно первый элемент массива. Составим программу на C++ для решения данной задачи.

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


Похожие записи:

Оставить комментарий

Ваш e-mail не будет опубликован. Обязательные поля отмечены *