Рубрики

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

Пререквизиты: декартово дерево

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

Например, рассмотрим массив {5, 10, 40, 30, 28}. Входные данные также частично отсортированы, так как только один обмен между «40» и «28» приводит к полностью отсортированному порядку. Посмотрите, как Cartesian Tree Sort воспользуется этим фактом ниже.

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

Шаг 1: Построить декартово дерево (с минимальной кучей) из заданной входной последовательности.

Шаг 2: Начиная с корня построенного декартового дерева, мы помещаем узлы в приоритетную очередь.
Затем мы помещаем узел в верхнюю часть приоритетной очереди и помещаем дочерние элементы выделенного узла в приоритетную очередь в порядке предварительного заказа.

  1. Поместите узел вверху очереди с приоритетами и добавьте его в список.
  2. Сначала нажмите на левого потомка вытолкнутого узла (если есть).
  3. Нажмите правый дочерний элемент выделенного узла следующим (если есть).

Как построить (мин-куча) декартово дерево?
Построение min-heap аналогично построению декартового дерева (max-heap) (обсуждалось в предыдущем посте ), за исключением того, что теперь мы сканируем вверх от родительского узла до корня дерева, пока не будет найден узел, значение которого равно меньше (и не больше, как в случае декартового дерева с максимальной кучей), чем текущее, а затем соответственно перенастроить связи для построения декартового дерева с минимальной кучей.

Почему бы не использовать только приоритетную очередь?
Кто-то может удивиться, что использование очереди приоритетов в любом случае приведет к сортировке данных, если мы просто вставим номера входного массива один за другим в очередь приоритетов (т.е. без построения декартового дерева).

Но затраченное время сильно отличается.

Предположим, мы берем входной массив — {5, 10, 40, 30, 28}

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

Принимая во внимание, что здесь мы можем видеть, что для использования декартового дерева потребовалось всего 5 операций (см. Две вышеупомянутые фигуры, на которых мы непрерывно нажимаем и ударяем узлы декартового дерева), что является линейным, поскольку во входном массиве также есть 5 чисел. Итак, мы видим, что лучший случай сортировки декартовых деревьев — это O (n), где сортировка кучи займет гораздо больше операций, потому что она не использует тот факт, что входные данные частично отсортированы.

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

Обратитесь к рисунку ниже для лучшего понимания

// Программа на C ++ для реализации сортировки декартовых деревьев
// Обратите внимание, что в этой программе мы создадим минимальную кучу
// Декартово дерево, а не макс-куча.
#include<bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct Node

{

    int data;

    Node *left, *right;

};

  
// Создание ярлыка для типа пары int, Node *

typedef pair<int, Node*> iNPair;

  
// Эта функция сортирует, нажимая и выталкивая
// Дерева декартовых деревьев в предзаказе, как в моде

void pQBasedTraversal(Node* root)

{

    // Мы будем использовать приоритетную очередь для сортировки

    // частично отсортированные данные.

    // В отличие от кучи, декартово дерево использует

    // тот факт, что данные частично отсортированы

    priority_queue <iNPair, vector<iNPair>, greater<iNPair>> pQueue;

    pQueue.push (make_pair (root->data,root));

  

    // напоминает ход предварительного заказа как первые данные

    // печатается затем левый и правый потомок.

    while (! pQueue.empty())

    {

        iNPair popped_pair = pQueue.top();

        printf("%d ",popped_pair.first);

  

        pQueue.pop();

  

        if (popped_pair.second->left != NULL)

            pQueue.push (make_pair(popped_pair.second->left->data,

                                   popped_pair.second->left));

  

        if (popped_pair.second->right != NULL)

             pQueue.push (make_pair(popped_pair.second->right->data,

                                    popped_pair.second->right));

    }

  

    return;

}

  

  

Node *buildCartesianTreeUtil(int root, int arr[],

           int parent[], int leftchild[], int rightchild[])

{

    if (root == -1)

        return NULL;

  

    Node *temp = new Node;

  

    temp->data = arr[root];

    temp->left = buildCartesianTreeUtil(leftchild[root],

                  arr, parent, leftchild, rightchild);

  

    temp->right = buildCartesianTreeUtil(rightchild[root],

                  arr, parent, leftchild, rightchild);

  

    return temp ;

}

  
// Функция для создания декартового дерева за O (N) время

Node *buildCartesianTree(int arr[], int n)

{

    // Массивы для хранения индекса parent, left-child,

    // правый потомок каждого числа во входном массиве

    int parent[n],leftchild[n],rightchild[n];

  

    // Инициализируем все значения массива как -1

    memset(parent, -1, sizeof(parent));

    memset(leftchild, -1, sizeof(leftchild));

    memset(rightchild, -1, sizeof(rightchild));

  

    // «корень» и «последний» хранит индекс корня и

    // последний обработан декартовым деревом.

    // Изначально мы укореняем декартово дерево как

    // первый элемент входного массива. Это может измениться

    // согласно алгоритму

    int root = 0, last;

  

    // Начиная со второго элемента входного массива

    // до последнего при сканировании по элементам, добавляя их

    // один за раз.

    for (int i=1; i<=n-1; i++)

    {

        last = i-1;

        rightchild[i] = -1;

  

        // Сканирование вверх от родительского узла до

        // корень дерева, пока не найден узел

        // значение которого меньше текущего

        // Это то же самое, что Шаг 2, упомянутый в

        // алгоритм

        while (arr[last] >= arr[i] && last != root)

            last = parent[last];

  

        // arr [i] - самый маленький элемент; сделай это

        // новый корень

        if (arr[last] >= arr[i])

        {

            parent[root] = i;

            leftchild[i] = root;

            root = i;

        }

  

        // Просто вставьте его

        else if (rightchild[last] == -1)

        {

            rightchild[last] = i;

            parent[i] = last;

            leftchild[i] = -1;

        }

  

        // Переконфигурируем ссылки

        else

        {

            parent[rightchild[last]] = i;

            leftchild[i] = rightchild[last];

            rightchild[last]= i;

            parent[i] = last;

        }

  

    }

  

    // Поскольку корень декартова дерева не имеет

    // родитель, поэтому мы присваиваем ему -1

    parent[root] = -1;

  

    return (buildCartesianTreeUtil (root, arr, parent,

                                    leftchild, rightchild));

}

  
// сортирует входной массив

int printSortedArr(int arr[], int n)

{

    // Построить декартово дерево

    Node *root = buildCartesianTree(arr, n);

  

    printf("The sorted array is-\n");

  

    // Выполнить прохождение заказа и вставить

    // в очереди приоритетов

    pQBasedTraversal(root);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    / * Заданный входной массив- {5,10,40,30,28},

        это соответствует уникальному декартовому дереву

        является-

  

        5

          /

          10

            /

             28

            /

          30

         /

        40

    * /

  

    int arr[] = {5, 10, 40, 30, 28};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    printSortedArr(arr, n);

  

    return(0);

}

Выход :

The sorted array is-
5 10 28 30 40

Сложность времени: O (n) поведение в лучшем случае (когда входные данные частично отсортированы), O (n log n) поведение в худшем случае (когда входные данные не отсортированы частично)

Вспомогательное пространство: мы используем очередь приоритетов и декартово древовидную структуру данных. Теперь в любой момент времени размер очереди с приоритетами не превышает размер входного массива, так как мы постоянно нажимаем и выталкиваем узлы. Следовательно, мы используем O (n) вспомогательное пространство.

Ссылки :
https://en.wikipedia.org/wiki/Adaptive_sort
http://11011110.livejournal.com/283412.html http://gradbot.blogspot.in/2010/06/cartesian-tree-sort.html http://www.keithschwarz.com/interesting/code/?dir = декартово-дерево-сортировка https://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting

Эта статья предоставлена Rachit Belwariar . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

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

0.00 (0%) 0 votes