Сортировка элементов по частоте с использованием двоичного дерева поиска

Дан массив целых чисел, отсортируйте массив по частоте элементов. Например, если входной массив {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, измените массив на {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.

В предыдущем посте мы обсудили все способы сортировки по частоте. В этом посте подробно обсуждается метод 2 и предоставляется его реализация на C++.
Ниже приведен подробный алгоритм.

• Создайте BST и при создании BST поддерживайте количество, то есть частоту каждого поступающего элемента в одном и том же BST. Этот шаг может занять время O(nLogn), если используется самобалансирующийся BST.
• Выполните обход BST по порядку и сохраните каждый элемент и количество каждого элемента во вспомогательном массиве. Назовем вспомогательный массив как 'count[]'. Обратите внимание, что каждый элемент этого массива является парой элемента и частоты. Этот шаг занимает O(n) времени.
• Сортировать count[] по частоте элементов. Этот шаг занимает время O(nLohn), если используется алгоритм сортировки O(nLogn).
• Пройдите через отсортированный массив 'count[]'. Для каждого элемента x выведите 'freq' раз, где 'freq' — это частота x. Этот шаг занимает O(n) времени.

Общая временная сложность алгоритма может быть минимальной O(nLogn) , если мы используем алгоритм сортировки O(nLogn) и используем самобалансирующийся BST с операцией вставки O(Logn) .
Ниже приведена реализация вышеописанного алгоритма.

Выход :

3 3 3 3 2 2 2 12 12 5 4

Сложность времени: O (n log n), так как выполняется быстрая сортировка.

Вспомогательное пространство: (n) для реализации BST.

Упражнение: приведенная выше реализация не гарантирует исходный порядок элементов с одинаковой частотой (например, 4 идет перед 5 на входе, но 4 идет после 5 на выходе). Расширьте реализацию, чтобы сохранить первоначальный порядок. Например, если два элемента имеют одинаковую частоту, выведите тот, который был первым во входном массиве.
Эта статья составлена Чандра Пракаш. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.