Merge sort tree in C++

We are given an integer array, a set of segment start and end pointers and a key value and the problem statement here is to find all the values ​​in the given range which are smaller than or equal to the given key value.

Let us understand with example

Input − arr[] = {7, 8 , 1, 4 , 6 , 8 , 10 }

Segment 1: start = 2, end = 4, k = 2

Segment 2: start = 1, end = 6, k = 3

Output − Count of number which are smaller than or equal to key value in the given range are 2 6

Explanation − [8, 1, 4] represents the range from 2 to 4 and 2 is the 2nd smallest number in the range [7, 8, 1, 4, 6, 8] represents the range from 1 to 6, 6 is the third smallest number in the range

Input - arr[] = {2 , 7 , 9, 4 , 6 , 5 , 1 |

Paragraph 1: starting position=3, ending position=6, k=4

Paragraph 2: starting position=2 , end position=5, k=3

Output - The number of numbers less than or equal to the key value in the given range is: 9 7

Explanation - [9, 4, 6, 5] represents the range from 3 to 6, 9 is the fourth smallest number in the given range [7, 9, 4, 6] represents the range from 2 to 4, 7 is the 3rd smallest number in the given segment range

The method used in the following program is as follows:

• Declare an array of integer type. Calculate the size of the array. Declare a variable of vector type, forming a pair of integer types. Start a FOR loop to push data from the array into the vector.

• Sort the given vector. Create a vector array of type integer with size MAX.

• Call the function generateTree(1, 0, size - 1, vec, tree), and set getSmallestIndex to queryWrapper(2, 5, 2, size, vec, tree).

• Print input[getSmallestIndex].

• Set getSmallestIndex to call function queryWrapper(1, 6, 4, size, vec, tree).

• Inside the function generateTree(int treeIndex, int leftIndex, int rightIndex, vector > &a, vector tree[])

  • Check IF leftIndex to rightIndex, then set tree[treeIndex].push_back(a[leftIndex].second) and return

  • Set midValue to (leftIndex rightIndex) / 2and call generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 * treeIndex 1, midValue 1, rightIndex, a, tree) and merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex 1 ].begin(). Set tree[2 * treeIndex 1].end(),back_inserter(tree[treeIndex]))

• Inside the function as int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[])

  • Check IF startIndex to endIndex then return tree[treeIndex][0 ]

  • Set mid to (startIndex endIndex) / 2, last_in_query_range to (upper_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin())

  • set first_in_query_range to (lower_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex]. end(), queryStart) - tree[2 * treeIndex].begin()) and M to last_in_query_range - first_in_query_range

  • Check IF M greater than equals to key then return calculateKSmallest(startIndex, mid, queryStart,queryEnd, 2 * treeIndex, key, tree)

  • ELSE, then return calculateKSmallest(mid 1, endIndex, queryStart, queryEnd, 2 * treeIndex 1, key - M, tree).

• Inside the function int queryWrapper(int queryStart, int queryEnd, int key, int n, vector > &a , vectortree[])

  • return call to the function calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree)

Example

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]){
   if (leftIndex == rightIndex){
      tree[treeIndex].push_back(a[leftIndex].second);
      return;
   }
   int midValue = (leftIndex + rightIndex) / 2;
   generateTree(2 * treeIndex, leftIndex, midValue, a, tree);
   generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree);
   merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(),
   tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex]));
}
int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[]){
      if (startIndex == endIndex){
         return tree[treeIndex][0];
      }
      int mid = (startIndex + endIndex) / 2;
      int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin());
      int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(),queryStart) - tree[2 * treeIndex].begin());
      int M = last_in_query_range - first_in_query_range;
      if (M >= key){
         return calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree);
      }
      else {
         return calculateKSmallest(mid + 1, endIndex, queryStart,queryEnd, 2 * treeIndex + 1, key - M, tree);
      }
}
int queryWrapper(int queryStart, int queryEnd, int key, int n,
   vector<pair<int, int> > &a, vector<int> tree[]){
      return calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree);
}
int main(){
   int input[] = { 7, 8 , 1, 4 , 6 , 8 , 10 };
   int size = sizeof(input)/sizeof(input[0]);
   vector<pair<int, int> > vec;
   for (int i = 0; i < size; i++) {
      vec.push_back(make_pair(input[i], i));
   }
   sort(vec.begin(), vec.end());
   vector<int> tree[MAX];
   generateTree(1, 0, size - 1, vec, tree);

   cout<<"Count of number which are smaller than or equal to key value in the given range are:"<<endl;

   int getSmallestIndex = queryWrapper(2, 4, 2, size, vec, tree);
   cout << input[getSmallestIndex] << endl;
   getSmallestIndex = queryWrapper(1, 6, 3, size, vec, tree);
   cout << input[getSmallestIndex] << endl;
   return 0;
}

Output

If we run the above code, the following output will be generated

Count of number which are smaller than or equal to key value in the given range are:
4
6

The above is the detailed content of Merge sort tree in C++. For more information, please follow other related articles on the PHP Chinese website!