Computer >> Máy Tính >  >> Lập trình >> C ++

Hợp nhất cây sắp xếp trong C ++

Chúng ta được cung cấp một mảng số nguyên, một tập hợp các con trỏ bắt đầu và kết thúc phân đoạn và một giá trị khóa và vấn đề ở đây là tìm tất cả các giá trị trong phạm vi đã cho nhỏ hơn hoặc bằng giá trị khóa đã cho.

Hãy cho chúng tôi hiểu với ví dụ

Đầu vào - arr [] ={7, 8, 1, 4, 6, 8, 10}

Phân đoạn 1:start =2, end =4, k =2

Phân đoạn 2:start =1, end =6, k =3

Đầu ra - Đếm số nhỏ hơn hoặc bằng giá trị chính trong phạm vi đã cho là 2 6

Giải thích - [8, 1, 4] đại diện cho phạm vi từ 2 đến 4 và 2 là số nhỏ thứ 2 trong phạm vi [7, 8, 1, 4, 6, 8] đại diện cho phạm vi từ 1 đến 6 và 6 là thứ 3 số nhỏ nhất trong phạm vi

Đầu vào - arr [] ={2, 7, 9, 4, 6, 5, 1 |

Phân đoạn 1:start =3, end =6, k =4

Phân đoạn 2:start =2, end =5, k =3

Đầu ra - Đếm số nhỏ hơn hoặc bằng giá trị khóa trong dãy đã cho là:9 7

Giải thích - [9, 4, 6, 5] đại diện cho phạm vi từ 3 đến 6 và 9 là số nhỏ thứ 4 trong phạm vi đã cho [7, 9, 4, 6] đại diện cho phạm vi từ 2 đến 4 và 7 là số nhỏ thứ 3 số trong phạm vi phân đoạn đã cho

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

  • Khai báo mảng kiểu số nguyên. Tính kích thước của một mảng. Khai báo một biến kiểu vectơ tạo thành cặp kiểu số nguyên. Bắt đầu vòng lặp FOR để đẩy dữ liệu từ mảng sang vectơ.

  • Sắp xếp các véc tơ đã cho. Tạo mảng vectơ gồm các kiểu số nguyên với kích thước TỐI ĐA.

  • Gọi hàm dưới dạng createTree (1, 0, size - 1, vec, tree) và đặt getSmallestIndex thành queryWrapper (2, 5, 2, size, vec, tree).

  • In đầu vào [getSmallestIndex].

  • Đặt getSmallestIndex để gọi hàm dưới dạng queryWrapper (1, 6, 4, size, vec, tree).

  • Bên trong hàm là void createTree (int treeIndex, int leftIndex, int rightIndex, vector > &a, vector tree [])

    • Kiểm tra NẾU leftIndex thành rightIndex, sau đó, đặt tên miền là [treeIndex] .push_back (a [leftIndex] .second) và trả về

    • Đặt midValue thành (leftIndex + rightIndex) / 2 và gọi createTree (2 * treeIndex, leftIndex, midValue, a, tree), createTree (2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) và hợp nhất (tree [2 * treeIndex] .begin (), tree [2 * treeIndex] .end (), tree [2 * treeIndex + 1] .begin (). Đặt tree [2 * treeIndex + 1] .end (), back_inserter (tree [ treeIndex]))

  • Bên trong hàm dưới dạng int allowmallest (int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree [])

    • Kiểm tra NẾU startIndex thành endIndex rồi trả về cây [treeIndex] [0]

    • Đặt mid thành (startIndex + endIndex) / 2, last_in_query_range thành (upper_bound (tree [2 * treeIndex] .begin (), tree [2 * treeIndex] .end (), queryEnd) - tree [2 * treeIndex] .begin ( ))

    • đặt first_in_query_range thành (low_bound (tree [2 * treeIndex] .begin (), tree [2 * treeIndex] .end (), queryStart) - tree [2 * treeIndex] .begin ()) và M thành last_in_query_range - first_in_query_range

    • Kiểm tra NẾU M lớn hơn bằng với khóa rồi trả về tính toán

    • ELSE, sau đó trả về allowmallest (mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree).

  • Bên trong hàm int queryWrapper (int queryStart, int queryEnd, int key, int n, vector > &a, vector tree [])

    • trả về lời gọi hàm tính toánKSmallest (0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree)

Ví dụ 

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau 

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