Phần tử K-th lớn nhất trong Max-Heap trong C++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm K-th phần tử lớn nhất từ max-heap.

Chúng ta sẽ sử dụng priority queue để giải quyết. Hãy xem các bước thực hiện.

• Khởi tạo max-heap với giá trị đúng.
• Tạo priority queue và chèn nút gốc của max-heap.
• Viết vòng lặp lặp K - 1 lần:
  • Loại bỏ phần tử lớn nhất khỏi queue.
  • Thêm nút trái và phải của nút trên vào priority queue.
• Phần tử lớn nhất trong priority queue là phần tử K-th lớn nhất.
• Trả về nó.

Ví dụ

Dưới đây là mã nguồn C++:

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

Kết quả

Nếu bạn chạy mã trên, kết quả sẽ là:

33

Kết luận

Nếu bạn có bất kỳ thắc mắc nào về hướng dẫn này, hãy để lại bình luận bên dưới.