หาค่ามากที่สุดลำดับที่ k ใน Max-Heap ใน C++

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมเพื่อหา k-th มากที่สุดจาก max-heap

เราจะใช้ priority queue เพื่อแก้ปัญหา มาดูขั้นตอนการเขียนโปรแกรม

• กำหนดค่าเริ่มต้นของ max-heap ด้วยค่าที่ถูกต้อง
• สร้าง priority queue และแทรกโหนดรากของ max-heap
• เขียนลูปที่วน k - 1 ครั้ง
  • Pop องค์ประกอบที่มากที่สุดออกจากคิว
  • เพิ่มโหนดซ้ายและขวาของโหนดด้านบนเข้าไปใน priority queue
• องค์ประกอบที่มากที่สุดใน priority queue คือค่ามากที่สุดลำดับที่ 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>> 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>{ 44, 42, 35, 33, 31, 19, 27, 10, 26, 14 }; 
    cout << findKthGreatestElement(heap, 4) << endl; 
    return 0; 
}

ผลลัพธ์

หากรันโค้ดด้านบน จะได้ผลลัพธ์ดังนี้:

33

สรุป

หากมีข้อสงสัยเกี่ยวกับบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็น