Tối Ưu Hàng Đợi Ưu Tiên (priority_queue) Trong C++

Xin chào anh em, lại là tôi - Jim đây!

Tôi tin rằng nhiều anh em ở đây đã từng trải qua cảm giác quen thuộc trên các đấu trường lập trình như Codeforces hay Leetcode. Anh em đối mặt với một bài toán đồ thị phức tạp, có thể là tìm đường đi ngắn nhất. Sau một hồi phân tích, anh em nảy ra một thuật toán Dijkstra chuẩn xác. Với sự tự tin, anh em nhanh chóng hiện thực hóa ý tưởng bằng priority_queue, một công cụ dường như hoàn hảo cho nhiệm vụ này. Anh em nộp bài, và... Time Limit Exceeded (TLE). Cảm giác thất vọng này có lẽ không hề xa lạ.

Tại sao một thuật toán đúng lại thất bại? Câu trả lời thường nằm ở những chi tiết hiệu năng ẩn sâu bên trong các công cụ mà chúng ta sử dụng hàng ngày. priority_queue là một vũ khí mạnh mẽ nhưng cũng đầy cạm bẫy trong kho tàng của một lập trình viên thi đấu. Bề ngoài, nó có vẻ đơn giản, nhưng hiệu năng thực tế lại bị chi phối bởi những yếu tố tinh vi, từ cấu trúc dữ liệu nền tảng đến cách bộ nhớ được quản lý.

Bài viết này sẽ là kim chỉ nam toàn diện, giúp anh em giải mã hoàn toàn priority_queue. Tôi sẽ đi từ những khái niệm cơ bản nhất, vạch trần những lầm tưởng phổ biến, cho đến việc khám phá những kỹ thuật tối ưu hóa bí mật mà các cao thủ thường sử dụng. Mục tiêu là biến priority_queue từ một cái bẫy TLE tiềm tàng thành một công cụ đáng tin cậy, giúp anh em chinh phục những bài toán khó nhằn nhất.

1. Giải Mã priority_queue

Để làm chủ bất kỳ công cụ nào, trước hết cần phải hiểu rõ bản chất của nó. priority_queue cũng không ngoại lệ. Việc nắm vững các nguyên tắc cơ bản sẽ là nền tóng cho các kỹ thuật tối ưu hóa nâng cao sau này.

1.1. Thực Chất Nó Là Gì? Bộ Điều Hợp Container

Một trong những hiểu lầm phổ biến nhất là coi priority_queue như một container độc lập giống vector hay list. Thực tế, nó là một container adapter (bộ điều hợp container). Điều này có nghĩa là nó không tự quản lý việc lưu trữ dữ liệu. Thay vào đó, nó bọc một container khác (gọi là container nền) và cung cấp một giao diện chuyên biệt. Mục đích cốt lõi của priority_queue là luôn đảm bảo truy cập đến phần tử có độ ưu tiên cao nhất trong thời gian hằng số (O(1)), đổi lại chi phí cho việc thêm và xóa phần tử là thời gian logarit (O(logN)). Điều này hoàn toàn trái ngược với hàng đợi thông thường (queue), vốn hoạt động theo nguyên tắc vào trước, ra trước (FIFO - First-In, First-Out).

1.2. Bên Dưới Lớp Vỏ: Cây Nhị Phân Vun Đống

Vậy làm thế nào priority_queue duy trì được trật tự ưu tiên một cách hiệu quả? Bí mật nằm ở cấu trúc dữ liệu mà nó sử dụng bên trong: một cây nhị phân vun đống (binary heap). Mặc định trong C++, priority_queue là một max-heap, nghĩa là phần tử lớn nhất luôn ở trên đỉnh. Khi anh em gọi các hàm như push() hay pop(), priority_queue sẽ tự động gọi các thuật toán heap tương ứng (push_heap, pop_heap) trên container nền để đảm bảo thuộc tính heap được duy trì. Việc đóng gói này giúp lập trình viên không cần phải quản lý heap thủ công, nhưng cũng che giấu đi những cơ chế quan trọng mà chúng ta có thể khai thác để tối ưu hóa.

1.3. Cú Pháp Cơ Bản: Max-Heap và Min-Heap

Việc khai báo một priority_queue khá đơn giản, nhưng có một điểm khác biệt quan trọng giữa max-heap (lấy ra phần tử lớn nhất) và min-heap (lấy ra phần tử nhỏ nhất).

• Max-Heap (Mặc định): Lấy ra phần tử có giá trị lớn nhất.

#include <bits/stdc++.h> using namespace std; int main()
{ priority_queue<int> max_pq; // ... return 0;
}

• Min-Heap (Cách chuẩn): Lấy ra phần tử có giá trị nhỏ nhất. Cần cung cấp thêm hai tham số template: container nền và hàm so sánh.

#include <bits/stdc++.h> using namespace std; int main()
{ priority_queue<int, vector<int>, greater<int>> min_pq; // ... return 0;
}

1.4. Phép So Sánh Ngược Đời

Một điểm gây bối rối kinh điển cho người mới bắt đầu: tại sao less<T> (mặc định) lại tạo ra max-heap, còn greater<T> lại tạo ra min-heap? Điều này có vẻ ngược đời. Lý do nằm ở định nghĩa thứ tự yếu nghiêm ngặt (strict weak ordering) mà priority_queue tuân theo. Phần tử top() của hàng đợi là phần tử mà khi so sánh với bất kỳ phần tử nào khác trong hàng đợi, hàm so sánh comp luôn trả về false.

Hãy phân tích logic này:

• Hàm so sánh mặc định là less<int>, tương đương với comp(a, b) trả về a < b.
• priority_queue sẽ đặt phần tử g lên đỉnh (top()) nếu comp(g, x) (tức là g < x) luôn là false với mọi phần tử x khác.
• Nếu g là phần tử có giá trị lớn nhất trong hàng đợi, thì g < x chắc chắn sẽ luôn false.
• Do đó, less tạo ra một max-heap. Ngược lại, greater (a > b) sẽ tạo ra một min-heap.

Hiểu rõ điều này không chỉ giúp tránh lỗi sai ngớ ngẩn mà còn cho thấy sự am hiểu sâu sắc về cách hoạt động của STL.

1.5. Các Thao Tác Thiết Yếu và Độ Phức Tạp

Dưới đây là các hàm thành viên quan trọng nhất và độ phức tạp thời gian của chúng:

2. Tùy Biến Cho Bài Toán Riêng

Trong lập trình thi đấu, chúng ta hiếm khi chỉ làm việc với các kiểu dữ liệu nguyên thủy. Thông thường, các bài toán đòi hỏi phải xử lý các đối tượng phức tạp hơn, ví dụ như các đỉnh trong đồ thị, các sự kiện trong một hệ thống mô phỏng, hay các trạng thái trong thuật toán tìm kiếm. Lúc này, priority_queue mặc định sẽ không hoạt động vì nó không biết cách so sánh các đối tượng tự định nghĩa này.

2.1. Phương Pháp 1: Nạp Chồng Toán Tử

Đây là phương pháp nhanh và đơn giản nhất, rất phù hợp trong môi trường thi đấu áp lực thời gian. Ta chỉ cần nạp chồng toán tử so sánh (thường là operator<) ngay bên trong struct hoặc class.

#include <bits/stdc++.h> using namespace std; struct Event
{ int time; string name; // Nạp chồng toán tử < // Để tạo min-heap theo 'time', ta cần định nghĩa sao cho // phần tử có 'time' lớn hơn được coi là "nhỏ hơn" (less). bool operator<(const Event& other) const { return time > other.time; }
}; int main()
{ // Khai báo như bình thường, nó sẽ tự động sử dụng operator< đã nạp chồng. priority_queue<Event> pq; // ... return 0;
}

• Ưu điểm: Rất nhanh để viết, cú pháp gọn gàng.
• Nhược điểm: Kém linh hoạt. Một class chỉ có thể có một cách nạp chồng operator< duy nhất, giới hạn việc sắp xếp theo các tiêu chí khác nhau.

2.2. Phương Pháp 2: Functor So Sánh

Đây là phương pháp chuẩn mực và linh hoạt hơn. Ta định nghĩa một struct riêng biệt, nạp chồng operator() (biến nó thành một functor - đối tượng hàm) để thực hiện việc so sánh.

#include <bits/stdc++.h> using namespace std; struct Event
{ int time; string name;
}; // Functor so sánh để tạo min-heap
struct CompareEvent
{ bool operator()(const Event& a, const Event& b) const { return a.time > b.time; }
}; int main()
{ // Cung cấp functor làm tham số template thứ ba priority_queue<Event, vector<Event>, CompareEvent> pq; // ... return 0;
}

• Ưu điểm: Cực kỳ linh hoạt. Tách biệt logic so sánh khỏi cấu trúc dữ liệu. Ta có thể tạo nhiều priority_queue của cùng một kiểu Event nhưng với các tiêu chí ưu tiên khác nhau (ví dụ, một cái theo thời gian, một cái theo độ dài tên).
• Nhược điểm: Dài dòng hơn một chút so với nạp chồng toán tử.

2.3. Phương Pháp 3: Biểu Thức Lambda

Với C++11 trở lên, biểu thức lambda cung cấp một cách viết comparator tại chỗ rất gọn gàng. Tuy nhiên, cú pháp khai báo priority_queue sẽ hơi phức tạp hơn một chút vì cần dùng decltype để lấy kiểu của lambda.

#include <bits/stdc++.h> using namespace std; struct Event
{ int time; string name;
}; int main()
{ // Định nghĩa lambda so sánh auto cmp = [](const Event& a, const Event& b) { return a.time > b.time; // Min-heap }; // Sử dụng decltype để lấy kiểu của lambda và truyền đối tượng lambda vào constructor priority_queue<Event, vector<Event>, decltype(cmp)> pq(cmp); // ... return 0;
}

• Ưu điểm: Gọn gàng cho các comparator đơn giản, định nghĩa ngay tại nơi sử dụng.
• Nhược điểm: Cú pháp có thể khó nhớ với người mới. Phù hợp nhất cho các hàng đợi ưu tiên dùng một lần, có phạm vi cục bộ.

3. Tối Ưu Hiệu Năng

Hiểu rõ cách sử dụng là một chuyện, nhưng để vượt qua giới hạn thời gian trong các kỳ thi, việc tối ưu hóa hiệu năng là tối quan trọng. Dưới đây là những kỹ thuật từ cơ bản đến nâng cao để ép từng mili giây ra khỏi priority_queue.

3.1. Điều Bắt Buộc: I/O Tốc Độ Cao

Trước khi nghĩ đến việc tối ưu cấu trúc dữ liệu, hãy đảm bảo rằng khâu nhập/xuất dữ liệu (I/O) không phải là nút thắt cổ chai. Với các bài toán có input lớn, I/O chậm có thể dẫn đến TLE ngay cả khi thuật toán của anh em tối ưu. Luôn thêm hai dòng thần thánh này vào đầu hàm main():

#include <bits/stdc++.h> using namespace std; int main()
{ ios_base::sync_with_stdio(false); cin.tie(NULL); // ... phần còn lại của chương trình return 0;
}

ios_base::sync_with_stdio(false); ngắt đồng bộ hóa giữa stream của C++ (cin/cout) và stream của C (scanf/printf), giúp tăng tốc đáng kể. cin.tie(NULL); gỡ bỏ sự ràng buộc giữa cin và cout, nghĩa là cin sẽ không phải đợi cout flush buffer trước khi đọc input.

Và một quy tắc vàng: Luôn dùng \n thay cho endl. endl không chỉ xuống dòng mà còn buộc cout phải flush (đẩy ra) buffer ngay lập tức, một thao tác rất tốn thời gian.

3.2. Khởi Tạo Cấp Tốc: O(N) và O(N log N)

Khi cần xây dựng một priority_queue từ một tập hợp N phần tử có sẵn (ví dụ, một vector), có hai cách tiếp cận với hiệu năng rất khác nhau.

• Cách chậm O(NlogN): Dùng vòng lặp và push() từng phần tử. Tổng thời gian sẽ là O(NlogN).

#include <bits/stdc++.h> using namespace std; int main()
{ vector<int> data = { /* N elements */ }; priority_queue<int> pq; for (int x : data) { pq.push(x); // Mỗi lần push tốn O(log i) } return 0;
}

• Cách nhanh O(N): Sử dụng constructor nhận vào cặp iterator. Constructor này sử dụng thuật toán make_heap bên trong, có độ phức tạp thời gian tuyến tính O(N).

#include <bits/stdc++.h> using namespace std; int main()
{ vector<int> data = { /* N elements */ }; priority_queue<int> pq(data.begin(), data.end()); return 0;
}

Tại sao make_heap lại nhanh như vậy? Thuật toán (thường là Floyd's algorithm) hoạt động bằng cách đi từ dưới lên. Nó bắt đầu từ nút không phải lá cuối cùng và vun đống xuống. Hơn một nửa số nút là lá (chiều cao 0), không tốn chi phí. Khoảng 1/4 số nút có chiều cao 1, 1/8 có chiều cao 2, và cứ thế. Tổng công việc là một chuỗi hội tụ về O(N). Đây là một tối ưu hóa cực kỳ quan trọng và dễ áp dụng. Nếu anh em có sẵn dữ liệu, luôn luôn sử dụng constructor.

3.3. Chọn Container Nền: Vector và Deque

priority_queue có thể được xây dựng trên vector (mặc định) hoặc deque. Lựa chọn nào tốt hơn?

• vector: Lưu trữ dữ liệu trong một vùng nhớ liền kề. Điều này mang lại tính cục bộ tham chiếu (cache locality) tuyệt vời.
• deque (hàng đợi hai đầu): Lưu trữ dữ liệu trong các khối nhớ không liền kề được liên kết với nhau.

Trong bối cảnh lập trình thi đấu, cache là vua. Các thao tác vun đống (push_heap, pop_heap) chủ yếu là hoán đổi các phần tử ở các chỉ số khác nhau. Với vector, các phần tử này có khả năng cao nằm gần nhau trong bộ nhớ, thậm chí trong cùng một dòng cache của CPU. Điều này giúp các thao tác hoán đổi diễn ra cực nhanh. Ngược lại, với deque, việc truy cập các phần tử có thể yêu cầu CPU nạp hai khối bộ nhớ hoàn toàn khác nhau, gây ra cache miss và làm chậm đáng kể.

Kết luận: Lợi ích về hiệu năng từ cache của vector gần như luôn vượt trội. Hãy gắn bó với vector mặc định trừ khi anh em có một lý do rất đặc biệt.

3.4. Lưu Con Trỏ và Lưu Đối Tượng

Khi anh em push một đối tượng vào priority_queue, một bản sao của đối tượng đó sẽ được tạo ra. Các thao tác vun đống liên tục hoán đổi các phần tử, dẫn đến nhiều lần sao chép hoặc di chuyển hơn nữa. Với các struct lớn chứa string hoặc vector, đây là một thảm họa về hiệu năng. Độ phức tạp của push thực chất là $O(\log N) \times (\text{chi phí so sánh} + \text{chi phí hoán đổi})$.

Giải pháp: Thay vì lưu trữ trực tiếp đối tượng, hãy lưu trữ con trỏ (hoặc con trỏ thông minh như unique_ptr) đến đối tượng.

#include <bits/stdc++.h> using namespace std; struct BigObject
{ //... rất nhiều dữ liệu... string data; vector<int> values; int priority;
}; int main()
{ // TỆ: Sao chép toàn bộ BigObject mỗi lần push/swap // priority_queue<BigObject> pq_objects; // TỐT: Chỉ sao chép con trỏ 8-byte auto cmp = [](const BigObject* a, const BigObject* b) { return a->priority < b->priority; // Max-heap theo priority }; priority_queue<BigObject*, vector<BigObject*>, decltype(cmp)> pq_pointers(cmp); // Đừng quên quản lý bộ nhớ (new/delete) khi dùng con trỏ thô! // Sử dụng unique_ptr/shared_ptr sẽ an toàn hơn. return 0;
}

Bằng cách này, chi phí hoán đổi trở nên không đáng kể, chỉ là hoán đổi hai địa chỉ bộ nhớ. Đây là một tối ưu hóa then chốt cho các bài toán có trạng thái phức tạp.

3.5. Trick Xóa Lười: Mô Phỏng Decrease-Key

Nhiều thuật toán kinh điển, nổi bật nhất là Dijkstra, yêu cầu một thao tác không được priority_queue hỗ trợ trực tiếp: decrease-key (giảm khóa), tức là tìm một phần tử trong hàng đợi và cập nhật độ ưu tiên của nó.

Giải pháp lười biếng (Lazy Deletion):

1. Đừng cố gắng tìm và cập nhật.
2. Thay vào đó, chỉ cần push một phiên bản mới, tốt hơn của phần tử đó vào hàng đợi.
3. Khi lấy phần tử ra từ top(), ta phải kiểm tra xem nó có lỗi thời không. Nếu có, chỉ cần bỏ qua và pop phần tử tiếp theo.

Đoạn mã cốt lõi trong thuật toán Dijkstra:

// dist[u] lưu khoảng cách ngắn nhất hiện tại tới đỉnh u
while (!pq.empty())
{ auto [d, u] = pq.top(); pq.pop(); // Đây là bước kiểm tra "xóa lười" if (d > dist[u]) { continue; } //... xử lý các đỉnh kề của u... // Nếu tìm thấy đường đi tốt hơn đến v: // dist[v] = new_dist; // pq.push({dist[v], v});
}

Kỹ thuật này làm tăng kích thước của hàng đợi (có thể lên tới $O(E)$ thay vì $O(V)$ trong Dijkstra), nhưng yếu tố logarit $O(\log E)$ về mặt tiệm cận tương đương với $O(\log V)$. Sự đơn giản và hiệu quả của nó đã biến nó thành kỹ thuật tiêu chuẩn phải biết trong lập trình thi đấu.

4. Các Lựa Chọn Thay Thế Đáng Gờm

Đôi khi, ngay cả priority_queue đã được tối ưu vẫn chưa đủ. May mắn thay, hệ sinh thái C++ cung cấp những lựa chọn khác, mỗi lựa chọn có những ưu và nhược điểm riêng.

4.1. priority_queue và set

Đây là một cuộc đối đầu kinh điển. Cả hai đều có thể được dùng để cài đặt Dijkstra.

Trong thực tế, các lập trình viên thi đấu hàng đầu thường chọn priority_queue. Lý do chính là hiệu năng cache. Bộ nhớ liền kề của vector giúp các thao tác heap nhanh hơn đáng kể so với việc truy cập các node phân mảnh trong bộ nhớ của set. Chi phí cho các phần tử lỗi thời trong priority_queue thường nhỏ hơn chi phí do cache miss của set.

4.2. Vũ Khí Bí Mật: __gnu_pbds::priority_queue

Đối với những ai tìm kiếm lợi thế tối đa, GNU Policy-Based Data Structures (PBDS) là một vũ khí bí mật. Đây là một thư viện mở rộng có sẵn trong trình biên dịch GCC/G++, vốn là tiêu chuẩn trên hầu hết các nền tảng thi đấu như Codeforces.

Ưu điểm lớn nhất của __gnu_pbds::priority_queue là nó hỗ trợ trực tiếp các thao tác modify() và erase(). Điều này giúp loại bỏ hoàn toàn sự phức tạp của trick xóa lười, làm cho mã nguồn cài đặt Dijkstra và Prim trở nên sạch sẽ và hiệu quả hơn.

Để sử dụng, anh em cần các dòng include sau:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp> // using namespace __gnu_pbds; // Đặt ở global scope

PBDS cung cấp nhiều loại heap khác nhau, được chọn thông qua một tag. Việc chọn đúng tag cho đúng bài toán là chìa khóa để tối ưu.

Đối với thuật toán Dijkstra chuẩn, ta luôn giảm khoảng cách, tức là tăng độ ưu tiên trong một min-heap. thin_heap_tag có độ phức tạp trung bình O(1) cho thao tác này, khiến nó trở thành lựa chọn nhanh nhất về mặt lý thuyết.

5. Thực Chiến: Áp Dụng Vào Bài Toán Kinh Điển

Lý thuyết sẽ trở nên vô nghĩa nếu không được áp dụng vào thực tế. Dưới đây là các ví dụ hiện thực hóa các kỹ thuật đã thảo luận.

5.1. Thuật toán Dijkstra

• Standard STL với Xóa Lười:

#include <bits/stdc++.h> using namespace std; const int INF = 1e9;
typedef pair<int, int> pii; // {distance, vertex} void dijkstra_stl(int start, int n, const vector<vector<pii>>& adj)
{ vector<int> dist(n + 1, INF); priority_queue<pii, vector<pii>, greater<pii>> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d > dist[u]) // Kỹ thuật xóa lười { continue; } for (auto& edge : adj[u]) { int v = edge.first; int weight = edge.second; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } // In kết quả...
}

• PBDS Upgrade:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp> using namespace std;
using namespace __gnu_pbds; const int INF = 1e9;
typedef pair<int, int> pii; // {distance, vertex}
typedef __gnu_pbds::priority_queue<pii, greater<pii>, thin_heap_tag> pbds_pq; void dijkstra_pbds(int start, int n, const vector<vector<pii>>& adj)
{ vector<int> dist(n + 1, INF); vector<pbds_pq::point_iterator> iterators(n + 1, nullptr); pbds_pq pq; dist[start] = 0; iterators[start] = pq.push({0, start}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (auto& edge : adj[u]) { int v = edge.first; int weight = edge.second; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; if (iterators[v] != nullptr) pq.modify(iterators[v], {dist[v], v}); else iterators[v] = pq.push({dist[v], v}); } } } // In kết quả...
} 

5.2. Tìm Phần Tử Lớn Thứ K

Một ứng dụng kinh điển khác là tìm phần tử lớn thứ K trong một luồng dữ liệu hoặc một mảng lớn với độ phức tạp O(NlogK).

#include <bits/stdc++.h> using namespace std; int find_kth_largest(const vector<int>& nums, int k)
{ // Dùng min-heap để lưu K phần tử lớn nhất priority_queue<int, vector<int>, greater<int>> min_heap; for (int num : nums) { if (min_heap.size() < k) { min_heap.push(num); } else if (num > min_heap.top()) { min_heap.pop(); min_heap.push(num); } } return min_heap.top();
}

5.3. Trộn K Danh Sách Đã Sắp Xếp

priority_queue cung cấp một giải pháp thanh lịch để trộn K danh sách đã được sắp xếp thành một danh sách duy nhất.

#include <bits/stdc++.h> using namespace std; // Giả sử có vector<vector<int>> lists;
vector<int> merge_k_lists(vector<vector<int>>& lists)
{ // Dùng min-heap lưu {value, list_index, element_index_in_list} priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq; // Đẩy phần tử đầu tiên của mỗi danh sách vào heap for (int i = 0; i < lists.size(); ++i) if (!lists[i].empty()) pq.push({lists[i][0], i, 0}); vector<int> result; while (!pq.empty()) { auto [value, list_idx, elem_idx] = pq.top(); pq.pop(); result.emplace_back(value); // Đẩy phần tử tiếp theo của danh sách vừa lấy ra vào heap if (elem_idx + 1 < lists[list_idx].size()) pq.push({lists[list_idx][elem_idx + 1], list_idx, elem_idx + 1}); } return result;
}

6. Lời Kết

priority_queue là một công cụ mạnh mẽ, nhưng sức mạnh thực sự của nó chỉ được bộc lộ khi người lập trình hiểu sâu sắc về cách nó hoạt động và cách tối ưu nó. Việc chỉ biết cú pháp cơ bản có thể dẫn đến những cái bẫy TLE không đáng có, trong khi việc nắm vững các kỹ thuật nâng cao có thể là yếu tố quyết định giữa một bài nộp Accepted và một bài nộp thất bại.

Để tóm tắt, đây là danh sách kiểm tra nhanh trước khi anh em bước vào một kỳ thi:

• 1. Luôn dùng Fast I/O: ios_base::sync_with_stdio(false); cin.tie(NULL); là bắt buộc.
• 2. Khởi tạo O(N): Nếu có sẵn dữ liệu, hãy dùng constructor pq(begin, end) thay vì push() trong vòng lặp.
• 3. Giữ vector làm container nền: Hiệu năng cache của nó gần như luôn là lựa chọn tốt nhất.
• 4. Lưu con trỏ cho đối tượng lớn: Tránh chi phí sao chép không cần thiết trong các thao tác heap.
• 5. Nắm vững Xóa Lười: Đây là kỹ thuật tiêu chuẩn để mô phỏng decrease-key trong các thuật toán như Dijkstra.
• 6. Sử dụng vũ khí bí mật PBDS: Khi cần hiệu năng tối đa và decrease-key thực sự, __gnu_pbds::priority_queue với tag phù hợp (như thin_heap_tag cho Dijkstra) là lựa chọn không đối thủ.

Kiến thức sâu về các cấu trúc dữ liệu cốt lõi và đặc tính hiệu năng thực tế của chúng là điều phân biệt giữa một lập trình viên giỏi và một lập trình viên xuất sắc. Hãy không ngừng thử nghiệm, đo lường và thực sự thấu hiểu các công cụ trong tay mình. Đó chính là con đường để chinh phục những đỉnh cao trong lập trình thi đấu. Hẹn gặp lại anh em trong các bài viết tiếp theo về chủ đề thuật toán và lập trình thi đấu!