Структуры данных и модели вычислений
Толстая куча
Толстая куча — это почти кучеобразный нагруженный лес.
Представление толстой кучи. Каждый узел толстой кучи будем представлять записью следующего вида:
где — ключ элемента, приписанного узлу дерева; — указатель на родителя; — указатель на ближайшего левого брата; — указатель на ближайшего правого брата; — указатель на самого левого сына; — ранг узла. Таким образом, "братья" связаны в двусвязный список при помощи указателей
и . У самого левого (правого) "брата" в этом списке указатель () заземлен.
На рис. 9.2 представлено толстое дерево
(внутри узлов указаны их ранги).
Рис. 9.2.
