Структуры данных и модели вычислений
Количество узлов высоты не превосходит
Утверждение 2.
Количество узлов высоты не превосходит .
Под высотой узла понимается расстояние от него до наиболее далекого потомка. Кучу, содержащую элементов, будем представлять двумя массивами — и , — полагая что — имя элемента, приписанного узлу ; — его ключ. Иногда под
удобно понимать сам элемент исходного множества или ссылку на него. В некоторых прикладных задачах нет необходимости помещать в приоритетную очередь ни сами элементы, ни их имена, в таких случаях при организации кучи используется лишь массив .
На рис. 4.1 приведен пример кучи для , . Кружочками изображены узлы дерева, в них записаны элементы массива, представляющие имена элементов кучи.
Пример кучи при , для приоритетной очереди, содержащей элементы с ключами , изображен на рис. 4.2, где пара чисел в каждом кружочке обозначает номер узла и ключ соответствующего элемента.
Рис. 4.1.
Рис. 4.2.
