Отыскание произвольного элемента в сортирующем дереве

Отыскание произвольного элемента в сортирующем дереве

Теперь осталось решить первоначальную проблему: эффективно найти элемент в сортирующем дереве. Эта проблема кажется неразрешимой - сортирующее дерево не содержит никакой вспомогательной информации, поскольку оно было разработано лишь для обеспечения эффективного поиска наибольшего элемента. Возврат к сбалансированному дереву двоичного поиска (при использовании которого для поиска элемента за время, пропорциональное O(log(n)), можно применить стандартный алгоритм поиска) кажется почти неизбежным.

Однако вместо этого мы создадим так называемое косвенное сортирующее дерево (indirect heap). При добавлении элемента в очередь по приоритету, управление этим элементом передается очереди. Взамен мы получаем дескриптор (handle). Дескриптор - это значение, по которому очередь "узнает" о добавлении элемента. Если хотите, дескриптор является косвенной ссылкой на реальный элемент в сортирующем дереве.

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

Для изменения приоритета элемента мы просто изменяем значение приоритета элемента и сообщаем очереди о том, что произошло, передавая ей дескриптор элемента. Затем очередь может восстановить свойство пирамидальное™. Операция исключения из очереди работает так же, как и ранее (дескриптор элемента не нужно передавать, поскольку очередь сама определит наибольший элемент). Однако очередь уничтожит дескриптор возвращенного элемента, поскольку он больше не присутствует в очереди. Если элементы являются записями или объектами, дескриптор данного элемента можно хранить внутри самого элемента наряду с приоритетом и другими полями.

В рамках операционной системы дескриптор, который, как правило, представляет собой своего рода замаскированный указатель, обычно имеет тип длинного целого. В рассматриваемой реализации мы используем всего лишь нетипизированный указатель.