ผสานการเรียงลำดับทรีใน C++

เราได้รับอาร์เรย์จำนวนเต็ม ชุดของจุดเริ่มต้นและจุดสิ้นสุดของเซ็กเมนต์ และค่าคีย์ และคำสั่งปัญหาที่นี่คือการค้นหาค่าทั้งหมดในช่วงที่กำหนดซึ่งน้อยกว่าหรือเท่ากับค่าคีย์ที่กำหนด

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − arr[] ={7, 8 , 1, 4 , 6 , 8 , 10 }

เซ็กเมนต์ 1:เริ่มต้น =2, สิ้นสุด =4, k =2

เซ็กเมนต์ 2:เริ่มต้น =1, สิ้นสุด =6, k =3

ผลผลิต − จำนวนตัวเลขที่น้อยกว่าหรือเท่ากับค่าคีย์ในช่วงที่กำหนดคือ 2 6

คำอธิบาย − [8, 1, 4] หมายถึงช่วงตั้งแต่ 2 ถึง 4 และ 2 เป็นตัวเลขที่เล็กที่สุดเป็นอันดับ 2 ในช่วง[7, 8 , 1, 4 , 6 , 8 ] แทนช่วงตั้งแต่ 1 ถึง 6 และ 6 คือช่วงที่ 3 จำนวนที่น้อยที่สุดในช่วง

ป้อนข้อมูล − arr[] ={2, 7 , 9, 4 , 6 , 5 , 1 |

เซ็กเมนต์ 1:เริ่มต้น =3, สิ้นสุด =6, k =4

เซ็กเมนต์ 2:เริ่มต้น =2, สิ้นสุด =5, k =3

ผลผลิต − จำนวนตัวเลขที่น้อยกว่าหรือเท่ากับค่าคีย์ในช่วงที่กำหนด ได้แก่ 9 7

คำอธิบาย − [9, 4 , 6 , 5] หมายถึงช่วงตั้งแต่ 3 ถึง 6 และ 9 เป็นตัวเลขที่เล็กที่สุดอันดับ 4 ในช่วงที่กำหนด[7 , 9, 4 , 6 ] แทนช่วงจาก 2 ถึง 4 และ 7 เป็นตัวเลขที่เล็กที่สุดเป็นอันดับ 3 ตัวเลขในช่วงเซ็กเมนต์ที่กำหนด

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

• ประกาศอาร์เรย์ประเภทจำนวนเต็ม คำนวณขนาดของอาร์เรย์ ประกาศตัวแปรประเภทเวกเตอร์สร้างคู่ของประเภทจำนวนเต็ม เริ่ม FOR วนซ้ำเพื่อส่งข้อมูลจากอาร์เรย์ไปยังเวกเตอร์

• เรียงลำดับเวกเตอร์ที่กำหนด สร้างอาร์เรย์เวกเตอร์ประเภทจำนวนเต็มที่มีขนาด MAX

• เรียกใช้ฟังก์ชันเป็น generateTree(1, 0, size - 1, vec, tree) และตั้งค่า getSmallestIndex เป็น queryWrapper(2, 5, 2, size, vec, tree)

• พิมพ์อินพุต[getSmallestIndex].

• ตั้งค่า getSmallestIndex ให้เรียกใช้ฟังก์ชันเป็น queryWrapper(1, 6, 4, size, vec, tree)

• ภายในฟังก์ชันเป็น void generateTree(int treeIndex, int leftIndex, int rightIndex, vector> &a, vector tree[])

  • ตรวจสอบ IF leftIndex เป็น rightIndex จากนั้น settree[treeIndex].push_back(a[leftIndex].second) และกลับ

  • ตั้งค่า midValue เป็น (leftIndex + rightIndex) / 2 และเรียก generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) และผสาน (tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin() ตั้งค่า tree[2 * treeIndex + 1].end(),back_inserter(tree[ treeIndex]))

• ภายในฟังก์ชันเป็น int คำนวณKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[])

  • ตรวจสอบว่า IF startIndex เป็น endIndex แล้วส่งคืน tree[treeIndex][0]

  • ตั้งค่า mid เป็น (startIndex + endIndex) / 2, last_in_query_range เป็น (upper_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin( ))

  • ตั้งค่า first_in_query_range เป็น (lower_bound(tree[2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) และ M เป็น last_in_query_range - first_in_query_range

  • ตรวจสอบว่า IF M มากกว่าค่าเท่ากับคีย์ จากนั้นส่งคืน calcKSmallest(startIndex, mid, queryStart,queryEnd, 2 * treeIndex, key, tree)

  • ELSE จากนั้นส่งคืน calcKSmallest(กลาง + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, คีย์ - M, tree)

• ภายในฟังก์ชัน int queryWrapper(int queryStart, int queryEnd, int key, int n, vector> &a, vectortree[])

  • ส่งคืนการเรียกฟังก์ชัน คำนวณKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree)

ตัวอย่าง

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

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

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