Heap là cấu trúc dữ liệu dạng cây nhị phân hoàn chỉnh, đảm bảo phần tử ở gốc luôn là lớn nhất (max-heap) hoặc nhỏ nhất (min-heap).
Hàng đợi ưu tiên (Priority Queue) là ứng dụng phổ biến nhất của heap — luôn lấy ra phần tử có độ ưu tiên cao nhất.
Độ phức tạp
| Thao tác | Độ phức tạp |
|---|---|
Thêm phần tử (push) |
|
Xóa phần tử lớn/nhỏ nhất (pop) |
|
Xem phần tử lớn/nhỏ nhất (top) |
|
| Xây dựng heap từ mảng |
Sử dụng trong C++
#include <queue>
// Max-heap (mặc định)
priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(4);
cout << pq.top(); // 4
pq.pop();
cout << pq.top(); // 3
// Min-heap
priority_queue<int, vector<int>, greater<int>> minpq;
minpq.push(3); minpq.push(1); minpq.push(4);
cout << minpq.top(); // 1
// Heap với pair
priority_queue<pair<int,int>> pq2;
pq2.push({5, 1}); pq2.push({3, 2});
cout << pq2.top().first; // 5
Sử dụng trong Python
import heapq
# Python chỉ có min-heap
h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
heapq.heappush(h, 4)
print(h[0]) # 1
heapq.heappop(h) # xóa và trả về 1
# Max-heap: đảo dấu giá trị
heapq.heappush(h, -5)
print(-h[0]) # 5
# Xây dựng heap từ list: O(N)
a = [3, 1, 4, 1, 5, 9]
heapq.heapify(a)
Ứng dụng
Thuật toán Dijkstra
vector<long long> dijkstra(int src, vector<vector<pair<int,int>>>& adj) {
int n = adj.size();
vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto [w, v] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
Tìm K phần tử lớn nhất
// Dùng min-heap kích thước K
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : a) {
pq.push(x);
if ((int)pq.size() > k) pq.pop();
}
// pq chứa K phần tử lớn nhất
Bình luận