Giả sử ta cần triển khai lớp MedianClass chứa các phương thức sau:
add(value): thêm giá trị vào cấu trúc dữ liệu.
median(): tìm trung vị của tất cả số hiện có trong cấu trúc dữ liệu.
Ví dụ: thêm 5, 3, 8 và tìm trung vị, kết quả 5.0; thêm 9 và tìm trung vị, kết quả 6.5.
Để giải quyết, ta làm theo các bước:
- Định nghĩa hàng đợi ưu tiên left (max-heap) và right (min-heap).
- Định nghĩa phương thức addNum nhận num:
- Nếu left rỗng hoặc num < đỉnh left, chèn num vào left.
- Ngược lại, chèn vào right.
- Nếu kích thước left < right: lấy đỉnh right, xóa khỏi right, chèn vào left.
- Nếu kích thước left - right > 1: lấy đỉnh left, xóa khỏi left, chèn vào right.
- Định nghĩa findMedian():
- Trả về đỉnh left nếu left.size() > right.size(), ngược lại trả về (đỉnh left + đỉnh right) / 2.
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; typedef double lli; class MedianClass { priority_queue <int> left; priority_queue <int, vector <int>, greater<int>> right; public: void addNum(int num) { if(left.empty() || num<left.top()){ left.push(num); }else right.push(num); if(left.size()<right.size()){ lli temp = right.top(); right.pop(); left.push(temp); } if(left.size()-right.size()>1){ lli temp = left.top(); left.pop(); right.push(temp); } } double findMedian() { return left.size()>right.size()?left.top():(left.top()+right.top())*0.5; } }; main(){ MedianClass ob; ob.addNum(5); ob.addNum(3); ob.addNum(8); cout << ob.findMedian() << " "; ob.addNum(9); cout << ob.findMedian() << endl; }
Đầu vào
ob.addNum(5); ob.addNum(3); ob.addNum(8); cout << ob.findMedian() << endl; ob.addNum(9); cout << ob.findMedian() << endl;
Đầu ra
5.0 6.5