Hàng đợi ưu tiên và Heap: giữ top K bằng C++ và Python

Hàng đợi ưu tiên khác FIFO thế nào?

Trong queue, phần tử đến trước được xử lý trước. Trong hàng đợi ưu tiên, phần tử có độ ưu tiên phù hợp nhất được chọn, dù nó đến muộn hơn. Ví dụ bài ghép đá yêu cầu luôn lấy hai viên nặng nhất; thứ tự đưa đá vào không quyết định hai viên được lấy.

Heap nhị phân biểu diễn một cây có các tầng đầy từ trái qua phải. Với min-heap, giá trị cha không lớn hơn giá trị con; vì thế gốc là phần tử nhỏ nhất. Với max-heap, chiều so sánh đảo lại. Quan hệ này không yêu cầu toàn bộ nhánh trái nhỏ hơn toàn bộ nhánh phải như cây tìm kiếm nhị phân.

Lưu heap trong mảng và hai thao tác sửa

Đánh chỉ số từ 0, con trái của i là 2*i + 1, con phải là 2*i + 2, cha là (i - 1) / 2 với i > 0. Hình dạng cây giúp lưu liên tiếp trong mảng mà không cần hai con trỏ ở mỗi nút. Chiều cao cây là O(log n), là cơ sở cho chi phí thêm và lấy đỉnh.

Khi thêm một số, đặt nó vào cuối mảng rồi đổi với cha nếu vi phạm quan hệ heap, tiếp tục đi lên. Khi lấy đỉnh, đưa phần tử cuối lên gốc rồi đẩy xuống qua người con phù hợp cho tới khi quan hệ được khôi phục. Chỉ những đường đi này cần sửa, không phải sắp xếp lại mọi phần tử.

Từ một mảng có sẵn, thao tác dựng heap như heapq.heapify có thời gian O(n). Thêm từng phần tử bằng n lần push có cận O(n log n). Hai cách có cùng mục tiêu nhưng cách phân tích tổng chi phí khác; không suy ra heapify cũng phải mất n log n chỉ vì bên trong có các lần đẩy xuống.

priority_queue C++ và heapq Python

priority_queue<int> mặc định của C++ là max-heap. Muốn min-heap dùng bộ so sánh greater<int> cùng bộ chứa vector. top() xem đỉnh, push() thêm và pop() xóa đỉnh không trả giá trị. Trước top/pop cần bảo đảm hàng đợi không rỗng.

Các hàm heappush, heappop của module heapq Python dùng min-heap và thay đổi list được truyền vào. heappop trả về giá trị vừa lấy. Không sửa ngẫu nhiên phần tử trong list rồi giả định nó còn là heap; khi dữ liệu đã bị đổi trực tiếp, cần khôi phục quan hệ heap thích hợp.

Bài giữ K phần tử lớn nhất

Cho luồng [7, 2, 9, 4, 9, 1] và K = 3. Muốn giữ ba số lớn nhất, ta phải sẵn sàng bỏ số nhỏ nhất trong nhóm đang giữ. Vì thế chọn min-heap, dù yêu cầu cuối cùng có chữ “lớn nhất”. Sau ba số đầu giữ 2, 7, 9; thêm 4 thì bỏ 2; thêm 9 thì bỏ 4; thêm 1 rồi loại chính 1.

Bất biến: sau mỗi lượt, heap giữ tối đa K số lớn nhất trong những số đã đọc. Nếu thêm số mới làm kích thước thành K+1, bỏ số nhỏ nhất là đủ. Những số đã loại không thể quay lại top K khi chỉ có thêm dữ liệu mới, vì hiện có ít nhất K số không nhỏ hơn chúng.

Code và cách đọc đầu ra

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <vector>
using namespace std;
vector<int> top_k(const vector<int>& a,int k){
    if(k<0)throw invalid_argument("k am");
    priority_queue<int,vector<int>,greater<int>> h;
    for(int x:a){h.push(x);if((int)h.size()>k)h.pop();}
    vector<int> ans;
    while(!h.empty()){ans.push_back(h.top());h.pop();}
    return ans; // tăng dần, tối đa min(k,n) phần tử
}
int main(){
    int n,k=3;vector<int>a={7,2,9,4,9,1};
    if(cin>>n>>k){a.resize(n);for(int&x:a)cin>>x;}
    for(int x:top_k(a,k))cout<<x<<' ';
    cout<<'\n';
}

import heapq

def top_k(a,k):
    if k<0:
        raise ValueError('k am')
    h=[]
    for x in a:
        heapq.heappush(h,x)
        if len(h)>k:
            heapq.heappop(h)
    return [heapq.heappop(h) for _ in range(len(h))]

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    a,k=(d[2:2+d[0]],d[1]) if d else ([7,2,9,4,9,1],3)
    print(*top_k(a,k))

Ví dụ mặc định in 7 9 9. Hai số 9 được giữ vì đây là top K phần tử theo số lần xuất hiện, không phải top K giá trị phân biệt. Muốn dữ liệu riêng, nhập n và K, tiếp theo n số nguyên. K = 0 trả danh sách rỗng; K lớn hơn n trả mọi phần tử hiện có. K âm bị từ chối.

Trong khi đọc n số, kích thước heap không vượt K+1 trước khi loại. Khi xuất, lấy liên tiếp từ min-heap cho thứ tự tăng dần, không phải thứ tự giảm dần. Nếu cần giảm dần, đảo kết quả sau cùng. Cũng đừng in trực tiếp list heap rồi gọi nó là dãy đã sắp xếp.

Độ phức tạp và cách tự kiểm

Gọi m = min(K,n). Phần duy trì có cận O(n log(m+1)); xuất m phần tử bằng cách pop hết cần O(m log(m+1)). Bộ nhớ ứng viên O(m), danh sách kết quả thêm O(m). Cách này có ích khi K nhỏ so với n hoặc dữ liệu đến dần. Nếu đã có toàn bộ mảng và cần gần hết phần tử, sắp xếp có thể đơn giản hơn.

Để tự kiểm tra trên dữ liệu nhỏ, bạn có thể sắp xếp toàn bộ mảng rồi lấy K phần tử lớn nhất để đối chiếu với kết quả từ heap trên các ca mảng rỗng, K = 0, K lớn hơn số phần tử, dãy tăng/giảm và các giá trị bằng nhau. Nếu đổi sang bài trả phần tử lớn thứ K, bạn cần quy ước khi n < K; không nên tự trả một số không có trong đề.

Các lỗi chọn cấu trúc và so sánh

Luyện ngay trên Big-O Coding

Ba bài lần lượt luyện phần tử lớn thứ K, lấy cực đại nhiều lượt và chọn K điểm có khoảng cách nhỏ nhất. Hãy xác định rõ cần giữ ứng viên nào và loại ứng viên nào trước khi chọn min-heap hoặc max-heap.

Câu hỏi thường gặp

Nguồn tham khảo

• cppreference: std::priority_queue
• Python: heapq
• Open Data Structures: BinaryHeap