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

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

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

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


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



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

  • Июнь
    2020
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31