Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

K'th Least Element ใน Min-Heap ใน C++


ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมที่หาองค์ประกอบที่น้อยที่สุดที่ k จาก min-heap

เราจะใช้ลำดับความสำคัญในการแก้ปัญหา มาดูขั้นตอนในการจบโปรแกรมกัน

  • เริ่มต้น min-heap ด้วยค่าที่ถูกต้อง
  • สร้างคิวลำดับความสำคัญและแทรกโหนดรูทของ min-heap
  • เขียนลูปที่วนซ้ำ k - 1 ครั้ง
    • แสดงองค์ประกอบที่น้อยที่สุดจากคิว
    • เพิ่มโหนดซ้ายและขวาของโหนดด้านบนลงในคิวลำดับความสำคัญ
  • องค์ประกอบที่ยิ่งใหญ่ที่สุดในคิวลำดับความสำคัญคือองค์ประกอบที่ยิ่งใหญ่ที่สุดลำดับที่ k ในขณะนี้
  • คืนสินค้า

ตัวอย่าง

มาดูโค้ดกันเลย

#include <bits/stdc++.h>
using namespace std;
struct Heap {
   vector<int> elemets;
   int n;
   Heap(int i = 0): n(i) {
      elemets = vector<int>(n);
   }
};
inline int leftIndex(int i) {
   return 2 * i + 1;
}
inline int rightIndex(int i) {
   return 2 * i + 2;
}
int findKthGreatestElement(Heap &heap, int k) {
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>queue;
   queue.push(make_pair(heap.elemets[0], 0));
   for (int i = 0; i < k - 1; ++i) {
      int node = queue.top().second;
      queue.pop();
      int left = leftIndex(node), right = rightIndex(node);
      if (left < heap.n) {
         queue.push(make_pair(heap.elemets[left], left));
      }
      if (right < heap.n) {
         queue.push(make_pair(heap.elemets[right], right));
      }
   }
   return queue.top().first;
}
int main() {
   Heap heap(10);
   heap.elemets = vector<int>{ 10, 14, 19, 24, 32, 41, 27, 44, 35, 33 };
   cout << findKthGreatestElement(heap, 4) << endl;
   return 0;
}

ผลลัพธ์

หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้

24

บทสรุป

หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น