Структуры данных и модели вычислений
Представление тонкой кучи в памяти компьютера.
Тонкие кучи формируют из узлов, представленных записями следующего вида:
где — ключ элемента, приписанного узлу; — указатель на ближайшего левого брата, если такового нет, то на родителя, а если нет и родителя, то указатель заземлен; — указатель на ближайшего правого брата, если такового нет, то указатель заземлен; — указатель на самого левого сына, если такового нет, то указатель заземлен; — ранг узла.
Таким образом, узлы-братья связаны в двусвязный список при помощи указателей и . У самого левого брата в этом списке указатель указывает на общего родителя всех узлов в списке. У самого правого брата из списка указатель заземлен. Корни деревьев в тонкой куче связаны в односвязный циклический список. Этот список будем называть корневым списком. Корневой список реализуется при помощи поля . Поле у каждого узла корневого списка заземлено.
В случае необходимости в описании узла может присутствовать и другая прикладная информация. На рис. 8.2 приведен пример тонкой кучи.
Тонкая куча
Представление кучи со ссылками, в узлах указаны ранги
Рис. 8.2.
Заметим, что принадлежность заданного узла корневому списку кучи осуществляется проверкой указателя на заземленность.
Введем еще одну запись , которая будет соответствовать отдельной куче и иметь вид
где — указатель на начальный элемент корневого списка; — указатель на элемент корневого списка с минимальным ключом.
Очевидно, что узел с минимальным ключом обязательно находится в корневом списке.
