Tóm tắt¶

Điểm lại trọng tâm¶

Đống (heap) là một cây nhị phân hoàn chỉnh. Tùy thuộc vào tính chất thỏa mãn, nó có thể được phân loại thành đống cực đại (max heap) hoặc đống cực tiểu (min heap). Phần tử ở đỉnh của đống cực đại (đống cực tiểu) là phần tử lớn nhất (nhỏ nhất).
Hàng đợi ưu tiên (priority queue) là một hàng đợi mà các phần tử trong đó được lấy ra theo độ ưu tiên, và nó thường được triển khai bằng đống.
Các thao tác phổ biến trên đống và độ phức tạp thời gian tương ứng bao gồm chèn phần tử \(O(\log n)\), xóa phần tử đỉnh \(O(\log n)\), và truy cập phần tử đỉnh \(O(1)\).
Cây nhị phân hoàn chỉnh rất phù hợp để biểu diễn bằng mảng, vì vậy chúng ta thường sử dụng mảng để lưu trữ đống.
Thao tác vun đống (heapify) được sử dụng để duy trì tính chất của đống và được áp dụng trong cả thao tác chèn và xóa phần tử.
Việc xây dựng đống (build heap) từ \(n\) phần tử đầu vào có thể được tối ưu hóa thành \(O(n)\), mang lại hiệu suất rất cao.
Bài toán Top-k là một bài toán thuật toán kinh điển có thể được giải quyết hiệu quả bằng cách sử dụng đống, với độ phức tạp thời gian là \(O(n \log k)\).

Q & A¶

Q: Thuật ngữ "đống" (heap) trong cấu trúc dữ liệu có cùng ý nghĩa với "đống" (heap) trong quản lý bộ nhớ không?

Chúng không phải là cùng một khái niệm, mà chỉ đơn giản là trùng tên gọi. Trong hệ thống máy tính, đống (heap) là một phần của cấp phát bộ nhớ động, và các chương trình có thể sử dụng nó để lưu trữ dữ liệu khi chạy. Chương trình có thể yêu cầu một lượng bộ nhớ đống nhất định để lưu trữ các cấu trúc phức tạp như các đối tượng và mảng. Khi dữ liệu không còn cần thiết, chương trình phải giải phóng vùng bộ nhớ đó để tránh rò rỉ bộ nhớ. So với bộ nhớ ngăn xếp (stack), bộ nhớ đống yêu cầu quản lý và sử dụng cẩn thận hơn; việc xử lý không đúng cách có thể dẫn đến các vấn đề như rò rỉ bộ nhớ và con trỏ lơ lửng.