Cтраница 1
Сортирующие деревья можно успешно использовать для решения проблемы выборки k максимальных элементов из N элементов ( см. главу 7), особенно в случаях, когда k мало. Мы просто прекращаем выполнение алгоритма пирамидальной сортировки после того, как k элементов будут отобраны из вершины сортирующего дерева. [1]
Биномиальные деревья и сортирующие деревья степени 2 эквивалентны. Мы будем работать с обоими представлениями, поскольку в своем воображении несколько легче построить зрительный образ биномиальные дерева, в то время как упрощенное представление сортирующих деревьев степени 2 приводит к более простой реализации. [2]
Другая идея заключается в том, чтобы построить сортирующие деревья, опираясь на представление полных пирамидально упорядоченных троичных деревьев в виде массивов, при этом узел в позиции k больше или равен узлам в позициях 3k - 1, 3k и 3k 1 и меньше или равен узлам в позициях ( ( & 1) / 3J для всех позиций между 1 и TV в массиве из N элементов. Снижение стоимости, обусловленное меньшей высотой дерева, уравновешивается более высокой стоимостью выбора наибольшего из трех потомков в каждом узле. Дальнейшее увеличение количества потомков в каждом узле по всем признакам не дает никакой выгоды. [3]
А ТД очередь по приоритетам могут быть реализованы через сортирующие деревья, такие, что для любой из указанных выше операций требуется выполнение не более чем 2 IgN операций сравнения на очереди из N элементов. [4]
В том случае, когда две объединяемые биномиальные очереди содержат только сортирующие деревья степени 2, размеры которых попарно различны, операция объединения есть ни что иное как слияние. [5]
Это делают, строя, начиная с листьев, все большие и большие сортирующие деревья. Всякое поддерево, состоящее из листа, уже является сортирующим. Чтобы сделать поддерево высоты h сортирующим, надо переставить элемент в корне с наибольшим из элементов, соответствующих его сыновьям, если, конечно, он меньше какого-то из них. Такое действие может испортить сортирующее дерево высоты h - 1, и тогда его надо снова перестроить в сортирующее. [6]
Структура данных биномиальной очереди Вийемана ( Vuillemin) в том виде, в каком она была реализована и исследована Брауном ( Brown), поддерживает все операции над очередями с приоритетами элегантно и эффективно. Двоичные сортирующие деревья, описанные Фредманом ( Fredman), Седжвиком, Слеатором ( Sleator) и Тарь-яном ( Tarjan), являются усовершенствованиями базового понятия и представляют немалый практический интерес. [7]
Более эффективным, нежели построение сортирующего дерева за счет последовательного выполнения вставок, как показано на рис. 9.5 и 9.6, является построение такого дерева методом прохождения по этому дереву в обратном направлении, формируя поддеревья меньших размеров снизу верх, что иллюстрирует рис. 9.9. Другими словами, мы рассматриваем каждую позицию массива как корень небольшого поддерева и извлекаем пользу из того обстоятельства, что функция fixDown работает на таких сортирующих поддеревьях столь же хорошо, как и на большом дереве. Если оба потомка узла суть сортирующие деревья, то вызов для этого узла функции fixDown приводит к тому, что поддерево с корнем в этом узле также становится сортирующим деревом. [8]
Можно также реализовать операцию удалить наибольший ( remove the maximum) путем одного вызова операции объединить. Для нахождения максимального элемента в биномиальной очереди просматриваются сортирующие деревья степени 2 этой очереди. Каждое такое дерево - левостороннее пирамидально упорядоченное сортирующее дерево, следовательно, максимальный его элемент находится в корне. Больший из корневых элементов является наибольшим элементом биномиальной очереди. [9]
Если в табличном представлении произвести лексикографическое упорядочение и сделать склейку по совпадающим префиксам, то получается древовидное представление данных, в основе которого лежит понятие дерева. Такое представление ведет к большей компактности данных и к ускорению поиска нужных данных. Такие древовидные структуры, как бинарные деревья, 2 - 3-деревья, В-деревья, сортирующие деревья [10] используются для внутреннего представления данных. Древовидное представление удобно использовать в лингвистических и подобных им БД, например, когда надо найти то или иное слово. Древовидное представление все еще достаточно просто для понимания, хотя и не так наглядно как табличное. [10]
Если в табличном представлении произвести лексикографическое упорядочение и сделать склейку по совпадающим префиксам, то получается древовидное представление данных, в основе которого лежит понятие дерева. Такое представление ведет к большей компактности данных и к ускорению поиска нужных данных. Такие древовидные структуры, как бинарные деревья, 2 - 3-деревья, В-деревья, сортирующие деревья [10] используются для внутреннего представления данных. Древовидное представление удобно использовать в лингвистических и подобных им БД, например, когда надо найти то или иное слово. Древовидное представление все еще достаточно просто для понимания, хотя и не так наглядно как табличное. [11]
Время выполнения пирамидальной сортировки не слишком чувствительно к природе входных данных. Независимо от того, какие значения принимают входные величины, наибольший элемент обнаруживается за число шагов, меньшее IgN. Вторая диаграмма сверху демонстрирует сортирующее дерево, построенное с помощью восходящего алгоритма, остальные диаграммы отображают для каждого файла процесс нисходящей сортировки. Вначале сортирующие деревья отображают в какой-то степени исходный файл, но по мере продвижения процесса сортировки они все больше напоминают сортирующие деревья, полученные для файла с произвольной организацией. [12]
Время выполнения пирамидальной сортировки не слишком чувствительно к природе входных данных. Независимо от того, какие значения принимают входные величины, наибольший элемент обнаруживается за число шагов, меньшее IgN. Вторая диаграмма сверху демонстрирует сортирующее дерево, построенное с помощью восходящего алгоритма, остальные диаграммы отображают для каждого файла процесс нисходящей сортировки. Вначале сортирующие деревья отображают в какой-то степени исходный файл, но по мере продвижения процесса сортировки они все больше напоминают сортирующие деревья, полученные для файла с произвольной организацией. [13]
Для биномиальных очередей характерно высокое быстродействие, тем не менее, были предложены специальные структуры данных, которые обладали в теоретическом плане еще лучшими характеристиками, гарантировано обеспечивая постоянное время выполнения некоторых операций. Эта проблема вызывает интерес и предлагает разработчиками структур данных широкое поле деятельности. С другой стороны, практическое применение многих из этих, понятных только посвященным, структур весьма сомнительно, а мы должны знать, что от некоторых имеющих место ограничений эффективности можно избавиться только путем снижения времени выполнения некоторых операций на очередях по приоритетам, прежде чем пускаться на поиски сложных решений в области структур данных. И в самом деле, для практических применений предпочтение следует отдавать тривиальным структурам при отладке и при работе с очередями малых размеров; далее, для ускорения операций, если речь не идет о получении быстродействующей операции объединить, необходимо использовать сортирующие деревья. Наконец, биномиальными очередями следует пользоваться, если требуется получить логарифмическое время выполнения всех операций. Однако, принимая во внимание все сопутствующие факторы, приходим к выводу, что пакет очередей по приоритетам на базе биномиальных очередей является, несомненно, ценным вкладом в библиотеку программного обеспечения. [14]