C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm



Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm

- Implements Order-Statistic tree.
- It is an improvement in BST by adding two more key functions- rank() and select().
- The time complexity of Order-statistic tree generation is O(n+n*log(n)).
- Once the tree is constructed, this algorithm takes O(log(n)) to find Kth largest number.

- Construct Order-Statistic tree for the given unsorted data array.
- Using the select function get the kth largest number from the given data set.
- Print the result.
- Exit.

#include<iostream>
 
using namespace std;
 
static int count = 0;
 
// A structure representing a node of a tree.
struct node
{
	int data;
	int rank;
	node *left;
	node *right;
};
 
// A function creating new node of tree and assigning the data.
node* CreateNode(int data)
{
	node *newnode = new node;
	newnode->data = data;
	newnode->rank = 0;
	newnode->left = NULL;
	newnode->right = NULL;
 
	return newnode;
}
 
// A function to create binary search tree.
node* Insert(node* root, int data)
{
	// Create node using data from argument list.
	node *temp = CreateNode(data);
	node *t = new node;
	t = root;
 
	// If root is null, assign it to the node created.
	if(root == NULL)
		root = temp;
	else	
	{	
		// Find the position for the new node to be inserted.
		while(t != NULL)
		{	
			if(t->data < data )
			{
				if(t->right == NULL)
				{
					// If current node is NULL then insert the node.
					t->right = temp;
					break;
				}
				// Shift pointer to the left.
				t = t->right;
			}
 
			else if(t->data > data)
			{
				if(t->left == NULL)
				{
					// If current node is NULL then insert the node.
					t->left = temp;
					break;
				}
				// Shift pointer to the left.	
				t = t->left;
			}
		}
	}
	return root;
}
 
// A function to assign a rank to each node of the tree.
void AssignRank(node *root)
{
	if(root->left != NULL)
		AssignRank(root->left);
 
	root->rank = count;
	count++;
 
	if(root->right != NULL)
		AssignRank(root->right);
}
 
// A function to search Kth smallest element from the data stored in the tree.
int Select(node* root, int k)
{
	// Search for the entered rank and shift the pointer accordingly, if rank not matched.
	if(root->rank == k)
		return root->data;
	else if(root->rank > k)
		return Select(root->left, k);
	else
		return Select(root->right, k);
}
 
// A function to take an inorder traversal of the tree and print the tree data of each node.
void print(node *root)
{
	if(root->left != NULL)
		print(root->left);
 
	cout<<"\n data: "<<root->data<<"    rank: "<<root->rank;
 
	if(root->right != NULL)
		print(root->right);
}
 
int main()
{
	char ch;
	int n, i, k, a[20]={40, 54, 96, 1, 9, 66, 78, 73, 36, 74, 44, 23, 35, 96, 38, 41, 49, 88, 27, 97};
	node *root = new node;
	root = NULL;
 
	// Construct the BST.
	for(i = 0; i < 20; i++)
		root = Insert(root, a[i]);
 
	cout<<"Enter the k value: ";
	cin>>k;
 
	// Assign rank to each of the nodes of the Binary Search tree.
	AssignRank(root);
 
	// Inorder traversal of the tree and displaying the data and the rank corresponding to that data.
	cout<<"\nRank associated to each node:-";
	print(root);
 
	// Print the result.
	cout<<"\n\nThe kth Largest element is: "<<Select(root, 20-k);
 
	return 0;
}