Sort elements by frequency using BST
Follow the given steps to solve the problem:
- Insert elements in BST one by one and if an element is already present then increment the count of the node. The node of the Binary Search Tree (used in this approach) will be as follows.
class tree {
public:
int element;
int first_index; /*To handle ties in counts*/
int count;
}
tree BST;
struct tree {
int element;
int first_index /*To handle ties in counts*/
int count;
} BST;
static class tree {
int element;
int first_index; /*To handle ties in counts*/
int count;
}
tree BST = new tree();
// This code is contributed by gauravrajput1
# Python code to implement the approach
class Tree:
element = None
# to handle ties
first_index = None
count = None
BST = Tree()
# This code is contributed by phasing17
public class tree {
public int element;
public int first_index; /* To handle ties in counts */
public int count;
}
tree BST = new tree();
// This code is contributed by gauravrajput1
// JS code to implement the approach
class tree {
constructor()
{
this.element;
this.first_index; //To handle ties in counts
this.count;
}
};
// This code is contributed by phasing17
- Store the first indexes and corresponding counts of BST in a 2D array.
- Sort the 2D array according to counts (and use indexes in case of a tie).
Implementation of the this approach: Set 2
Time Complexity: O(N log N) if a Self Balancing Binary Search Tree is used.
Auxiliary Space: O(N)
Sort elements by frequency
Print the elements of an array in the decreasing frequency if 2 numbers have the same frequency then print the one which came first
Examples:
Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}