Сортировка декартовым деревом

    Свежий взгляд на традиционные концепции. Сегодня будет такой «декарт» которого в школе не проходили.


    Суть алгоритма в том, что на основании массива строится так называемое декартово дерево. А из построенного декартового дерева очень легко получить все элементы в порядке возрастания или убывания.
    EDISON Software - web-development
    Компания EDISON всегда рада приобщиться к прекрасному.


    Один из наших классических проектов — диагностика хранилища документов Vivaldi, благодаря чему оптимизирован одновременный доступ к тысячам документам и произведениям в сетевой библиотеке.

    Мы очень любим сеять разумное, доброе, вечное! ;-)
    В рамках этой статьи я решил воздержаться от подробной теории и не стану разъяснять, что такое декартово дерево, как его построить и какие с ним возможны операции. Это уже прекрасно сделано и до меня — на Хабре есть превосходный материал, где все эти моменты удачно и подробно освещены — в конце этой лекции есть раздел «Ссылки», где можно перейти к этим хабрастатьям. В дальнейшем я буду освещать некоторые моменты, характерные для этой структуры, но при этом подразумевается, что вы понимаете её специфику или, в случае заинтересованности, готовы её изучить по указанным ниже ссылкам.

    Декартово дерево является гибридной структурой, объединяющей в себе свойства кучи и бинарного дерева поиска. Для этого дерева есть синонимы, которые будут использоваться в статье:

    дерамида (дерево + пирамида),
    трип (treaptree + heap)
    и даже дуча (дерево + куча).

    Давайте возьмём для примера вот этот массив:



    и последовательно взглянем, как для него выглядит двоичное дерево поиска, куча и дерамида.

    Бинарное дерево поиска




    Внешний вид дерева сильно зависит от того, как изначально расположены элементы массива. На рандомных данных, дерево с высокой долей вероятности получится несбалансирвоанным, с гораздо большим количеством уровней, по сравнению с оптимальным. В нашем примере образовалось 7 уровней. Если бы элементы массива располагались, например, в таком порядке:

    25, 28, 29, 23, 30, 27, 24, 22, 21, 26

    дерево поиска бы получилось сбалансированным, с минимально возможным количеством уровней (= 4). Сортировка с помощью сбалансированного дерева имела бы сложность по времени: O(n log n). Но в случае несбалансированного дерева может деградировать и до O(n2).

    В предыдущей хабрастатье рассмотрена сортировка бинарным деревом поиска, а также её интересная модификация, позволяющая гарантировано сортировать с временно́й сложностью O(n log n).

    Чем более несбалансированным будет дерево поиска, тем более затратным будет его обход.

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

    Родитель в двоичном дереве поиска необязательно больше чем потомок. Но при этом левый потомок всегда меньше родителя, правый потомок всегда больше родителя (или равен ему).

    Максимальный элемент массива при построении дерева поиска попадает где-то в правое поддерево. Чтобы этот максимум извлечь, дерево поиска надо полностью обойти.

    Бинарная куча


    В обычной куче очень просто организованы взаимосвязи «родитель — потомок», они привязаны к самим индексам элементов.



    На рисунке на самом деле пока ещё не куча, поскольку такое дерево, изначально построенное на рандомном массиве ещё не является сортирующим. Нужно обойти каждый элемент и сделать для него просейку. В результате элементы в массиве перестроятся так, что каждый родитель будет больше своего потомка:



    Максимальный элемент находится в корне дерева. Его расположение известно, его искать не нужно. С другой стороны, при если извлечь максимум из кучи (и вместо него в корень дерева приходится ставить какой-то другой элемент массива), куча перестаёт быть сортирующим деревом, её нужно опять просеивать.

    Декартово дерево


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



    С другой стороны, структура является бинарным деревом поиска, если смотреть на индексы элементов. На изображении в дереве для наглядности убрали в узлах значения элементов, оставили только индексы. Каждый левый потомок меньше родителя, каждый правый потомок — больше родителя:



    С одной стороны, мы имеем быстрый доступ к максимальному элементу. Так как это куча, то максимум находится в корне.

    С другой стороны, из структуры легко можно удалить максимум и работать с оставшимися данными дальше. Так как это бинарное дерево поиска, удаление корня не связано с большими затратами. Во взаимосвязях «родители-потомки» происходят относительно небольшие изменения, в корень декартова дерева попадает новый максимум и можно работать дальше.

    Каждый элемент характеризуется двумя числами — значением элемента и индексом элемента в массиве. Индекс можно считать за координату X, значение — за Y, а сам элемент интепретировать как точку на координатной плоскости. Если родителей и потомков соединить стрелками, то получается примерно такая картина:


    Фигура на графике полностью изоморфна декартову дереву чуть выше.

    Сортировка декартовым деревом :: Cartesian tree sort


    Итоговый алгоритм:

    • I. На основании неотсортированного массива строим декартово дерево:
      • I.1. Перебираем элементы массива слева-направо.
      • I.1. Если это первый элемент массива, то он просто является самым первым узлом декартова дерева.
      • I.2. Если это не первый элемент массива, считаем что это декартово дерево, состоящее из одного элемента. Производим операцию Merge этого дерева с тем деревом, которое построено из предыдущих элементов.
    • II. Текущий максимальный элемент удаляем из дерева, после чего восстанавливаем декартово дерево.
      • II.1. Текущий максимальный элемент — корень дерева.
      • II.2. Удаляем из дерева корень, сам максимальный элемент переносим в дополнительный массив.
      • II.3. После удаления корня структура распалось на два декартова дерева.
      • II.4. Для этих двух деревьев производим операцию Merge. Новым текущим максимумом становится один из корней объединяемых деревьев.
      • II.5. Для нового максимума снова повторяем действия II.1-II.4.



    Сложность


    Декартово дерево с минимальными затратами обрабатывает отсортированные и почти отсортированные (причём неважно, по возрастанию или убыванию) участки массива. Вот, например, так выглядит процесс для реверсно упорядоченного массива:



    Самая затратная часть алгоритма — это операция Merge, которую для каждого из n элементов приходится делать дважды — сначала при построении дерамиды и затем при её разборке. На рандомных данных однократная операция Merge обходится в O(log n), но для элементов, находящихся в упорядоченных областях массива стоимость операции O(1).

    Таким образом, средняя и худшая временна́я сложность сортировки — O(n log n), лучшая — O(n).

    По дополнительной памяти дела обстоят похуже — O(n). Если бы декартово дерево было просто разновидностью кучи, то затраты были бы O(1). Но cartesian tree — это также и дерево бинарного поиска, из-за чего для всех n элементов приходится отдельно хранить взаимосвязи «родители-потомки».

    Кроме того, реализация именно в таком виде означает, что это внешняя сортировка — отсортированные элементы собираются в отдельном массив. А это ещё O(n) по дополнительной памяти.

    Ссылки


    Cartesian

    Декартово дерево: Часть 1, Часть 2, Часть 3

    Статьи серии:



    В приложение AlgoLab добавлена сегодняшняя сортировка декартовым деревом, кто пользуется — обновите excel-файл с макросами. Рекомендую брать массивы с небольшим разбросом в значениях элементов — иначе декартова плоскость не будет помещаться на экране.
    Edison
    Изобретаем успех: софт и стартапы

    Comments 6

      +4

      Я не понял смысл происходящего. Либо у вас тут на самом деле завуалированная сортировка кучей (в коде встречается priority_queue и не встречается Merge), либо вы никак не доказали O(n log n) в худшем случае. И на самом деле там легко может быть O(n^2), как у QuickSort с фиксированным выбором медианы.


      1. Зачем вы вводите операцию Merge, хотя в предоставленной реализации на C++ её нет и вместо неё используется priority_queue — очередь с приоритетом, которая в стандартной библиотеке C++ реализована как обычная двоичная куча?
      2. Если вы хотели использовать priority_queue вместо Merge с самого начала, то зачем вообще вводить декартово дерево? Асимптотику это никак не улучшает — в худшем случае в очереди будет лежать O(n) элементов, получаем в точности сортировку кучей, но в которую зачем-то добавили O(n) лишней памяти.
      3. Если вы всё-таки хотите использовать стандартный Merge, который проходит по двум деревьям сверху вниз и склеивает их, то откуда вы взяли оценку в O(log n) на операцию в среднем и уж тем более в худшем варианте?

      Это точно не декартово дерево в обычном смысле: для любых классических вариантов декартова дерева (в том числе по неявному ключу) требуется рандом (случайные величины). Обычно его ставят как раз в приоритеты (высоты) вершин, которые вы взяли из входных данных. У вас рандома нет вообще.


      И именно из рандома во всех оценках берутся разумные слова "в среднем": в среднем по случайно сгенерированным приоритетам вершин, то есть в среднем по нескольким запускам программы на одних и тех же входных данных. Но у вас "в среднем" получается по входным данным. Примерно как детерминированный QuickSort — на случайных данных работает, на специально подогнанных — O(n^2).

        +2

        Спасибо автору статьи за ссылку на (вероятно) исходный пост в комментарии ниже.


        Там как раз автор не использует никакой Merge в объяснении времени работы и чётко говорит, что это именно оптимизация для сортировки кучей почти отсортированных массивов, а декартово дерево тут вообще побоку. И оценки на время работы к декартову дереву не относятся никак.


        Там же автор ссылается на исходную статью Heapsort—Adapted for presorted files 1989 года, в которой этот алгоритм (улучшение сортировки кучей) изучают, придумывают метрику для оценки "отсортированности" массива (называют Osc) и показывают интересную границу времени работы через эту метрику. Это оказывается лучше, чем O(n log n), для некоторых отсортированных массивов. И заодно авторы доказывают, что по этой метрике быстрее сортировать невозможно.


        Но из текущего поста это понять решительно невозможно.

        +2

        Хаб "Совершенный код" тоже выглядит странновато. Реализация выглядит "по-олимпиадному" в плохом смысле этого слова. Кажется, что автор кода C++ знает плохо или зачем-то решил убрать все детали, но для этого лучше вообще на питоне писать.


        • Полное отсутствие освобождения памяти. Использование чистых указателей и new. На контестах окей, в любом долгоживущем коде не окей. Хоть бы unique_ptr для владения детьми добавили.
        • CartesianTree(std::vector<int> ar) — передача по значению вместо константной ссылки. Лишнее копирование вектора целиком.
        • NULL вместо принятого с C++11 nullptr.
        • Присваивания в конструкторе вместо объявления поля int value = 0 (default member initializer) или хотя бы member initialization list в конструкторе (Node() : value(0) {}).
          0
          Код взял отсюда, но ок, я его, пожалуй, пока уберу. Чуть позже заменю на другой.
          +2
          А SkipList не пробовали использовать?

          Для своих задач пользую активно. Класстческий SkipList с расширением в виде виртуального номера элемента (т.е. поиск можно проводить не только по ключу, но и по позиции элемента в списке), который фактически является вторым ключом — алгоритм поиска по нему аналогичен алгоритму поиска по ключу.

          На базе этого алгоритма у меня созданы сортированный список (вместо пары ключ-данные есть только данные, которые одновременно являются ключом) и «набор» — список однотипных элементов.

          Дополнительно реализовал такие методы как поиск по частичному (первые n байт) ключа, переход к следующему/предыдущему элементу, у которого первые n байт ключа совпадают/не совпадают с первыми n байт ключа текущего элемента.

          Основная работа у нас с БД — использую для кеширования записей (в частности) чтобы лишний раз не дергать таблицу, по которой уже прошелся.

          Иногда для сортировки использую. Была одна задачка, где нужно было получить выборку, отсортированную по набору полей. Причем, поля эти неиндексированы. Решение в лоб, с использованием ORDER BY в SQL запросе давало время порядка минуты-полторы на выполнение всей задачи (там выборки по 50-60 и более тысяч записей). Убрал ORDER BY из запроса, а результаты выборки занес в SkipList с ключом из комбинации этих самых полей. Время выполнения той же задачи на тех же данных сократилось до 10-15 секунд

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

          Вставка-удаление тоже в среднем быстрее чем для деревьем т.к. не требует периодической перебалансировки дерева.
            +2
            Вот результаты теста. Заполнение SkipList записями из таблицы с уникальным ключом.
            Система IBM i (AS/400), 1 процессор IBM PowerS924, 18 ядер SMT8 (144 потока). 16Гб ОЗУ на задачу.

            При заполнении списка засечки времени делались по последним 100 000 элементам.
            При удалении — по первым 100 000 элементам.

            Поиск — максимальное и среднее время считалось по 100 000 элементам

            image

          Only users with full accounts can post comments. Log in, please.