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

2bbc099f

Толстая куча


Толстая куча — это почти кучеобразный нагруженный лес.

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

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

и . У самого левого (правого) "брата" в этом списке указатель () заземлен.

На рис. 9.2 представлено толстое дерево

(внутри узлов указаны их ранги).


Рис. 9.2. 



Содержание раздела