Классическая структура данных, используемая для создания очереди по приоритету, известна под названием сортирующего дерева (или "кучи"). Сортирующее дерево (heap), на которое еще ссылаются как на частично упорядоченное полное двоичное дерево, - это двоичное дерево с определенными специальными свойствами и несколькими специальными операциями. (Не путайте эту "кучу" с "кучей", используемой в среде Delphi, -областью памяти, в которой выполняется все распределение памяти.) В дереве двоичного поиска узлы организованы так, что каждый узел больше своего левого дочернего узла и меньше своего правого дочернего узла. Такое упорядочение называется строгим. В сортирующем дереве используется менее строгое упорядочение, называемое пирамидальным свойством. Пирамидальное свойство означает всего лишь, что любой узел в дереве должен быть больше обоих его дочерних узлов. Обратите внимание, что пирамидальное свойство ничего не говорит о порядке дочерних узлов данного узла. Например, оно не утверждает, что левый дочерний узел должен быть меньше правого дочернего узла.

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

Так как же эта структура может помочь в наших поисках идеальной структуры очереди по приоритету? Что ж, операции вставки и удаления при использовании сортирующего дерева являются операциями типа 0(log(«)), но они выполняются значительно быстрее, чем эти же операции в дереве двоичного поиска, независимо от того, является ли оно сбалансированным. Это тот случай, когда О-нотация оказывается неприемлемой - она не позволяет количественно определить, какая из двух операций с одним и тем же значением О большого действительно выполняется быстрее.

Вторая простая реализация || Оглавление || Вставка в сортирующее дерево


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Сентябрь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс