Структуры данных и модели вычислений


Представление тонкой кучи в памяти компьютера.


Тонкие кучи формируют из узлов, представленных записями следующего вида:

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

Таким образом, узлы-братья связаны в двусвязный список при помощи указателей и . У самого левого брата в этом списке указатель указывает на общего родителя всех узлов в списке. У самого правого брата из списка указатель заземлен. Корни деревьев в тонкой куче связаны в односвязный циклический список. Этот список будем называть корневым списком. Корневой список реализуется при помощи поля . Поле у каждого узла корневого списка заземлено.

В случае необходимости в описании узла может присутствовать и другая прикладная информация. На рис. 8.2 приведен пример тонкой кучи.


Тонкая куча

Представление кучи со ссылками, в узлах указаны ранги


Рис. 8.2. 

Заметим, что принадлежность заданного узла корневому списку кучи осуществляется проверкой указателя на заземленность.

Введем еще одну запись , которая будет соответствовать отдельной куче и иметь вид

где — указатель на начальный элемент корневого списка; — указатель на элемент корневого списка с минимальным ключом.

Очевидно, что узел с минимальным ключом обязательно находится в корневом списке.




Начало  Назад  Вперед