Trong lập trình, khi làm việc với các bộ sưu tập dữ liệu, chúng ta thường sử dụng các kiểu dữ liệu như danh sách, tập hợp, từ điển và hàng đợi. Tuy nhiên, ít ai biết đến kiểu dữ liệu đống (heap) - một kiểu dữ liệu mà rất ít khi được sử dụng.
Đống là gì?
Đống (heap) là một cấu trúc dữ liệu dựa trên cây có các tính chất sau: trong một đống tối đa (max-heap), giá trị của nút cha luôn lớn hơn hoặc bằng giá trị của nút con. Trong một đống tối thiểu (min-heap), giá trị của nút cha luôn nhỏ hơn hoặc bằng giá trị của nút con. Nút ở đỉnh của đống (không có nút cha) được gọi là nút gốc.
Đống được sử dụng rộng rãi như một triển khai hàng đợi ưu tiên. Trong một đống, phần tử có giá trị cao nhất (hoặc thấp nhất) luôn nằm ở nút gốc. Mặc dù đống không phải là một cấu trúc dữ liệu sắp xếp hoàn chỉnh, nó có thể được coi là một cấu trúc dữ liệu một phần được sắp xếp. Đối với những tác vụ cần loại bỏ đối tượng có mức ưu tiên cao nhất (hoặc thấp nhất) nhiều lần, đống là một cấu trúc dữ liệu hữu ích.
Ứng dụng của đống
Có nhiều loại đống được sử dụng, nhưng đống nhị phân là loại phổ biến nhất. Đống có vai trò quan trọng trong nhiều thuật toán liên quan đến đồ thị và sắp xếp.
Dưới đây là một số phép toán thường được thực hiện trên đống:
- Tìm phần tử lớn nhất (hoặc nhỏ nhất): tìm giá trị lớn nhất trong đống tối đa (tìm giá trị nhỏ nhất trong đống tối thiểu).
- Xóa phần tử lớn nhất (hoặc nhỏ nhất): xóa nút gốc của đống tối đa (đống tối thiểu).
- Tăng giá trị (giảm giá trị): thay đổi giá trị của một phần tử trong đống tối đa (đống tối thiểu).
- Chèn: chèn một giá trị mới vào trong đống.
- Hợp: kết hợp hai đống thành một đống mới chứa tất cả các giá trị của cả hai.
Thời gian thực hiện các phép toán trên đống nhị phân:
- Tìm giá trị lớn nhất: O(1)
- Xóa giá trị lớn nhất: O(log n)
- Chèn giá trị: O(log n)
- Tăng giá trị: O(log n)
- Hợp: O(n)
Ứng dụng tìm k phần tử lớn nhất
Khi cần tìm k phần tử lớn nhất (hoặc nhỏ nhất) trong n phần tử cho trước, thường chúng ta sắp xếp các phần tử theo thứ tự tăng dần (hoặc giảm dần) và lấy k phần tử đầu tiên. Tuy nhiên, phương pháp này không hiệu quả khi k nhỏ hơn n đáng kể. Bằng cách sử dụng kiểu dữ liệu đống, chúng ta có thể lấy ra k phần tử đó mà không cần phải sắp xếp toàn bộ danh sách.
Dưới đây là ví dụ về cách sử dụng kiểu dữ liệu đống trong Python:
-
Cách thường dùng:
klargest = sorted(iterable, reverse=True)[:k] -
Cách tối ưu:
import heapq klargest = heapq.nlargest(k, iterable)
Kết luận
Đống là một kiểu dữ liệu cơ bản mà hầu hết các ngôn ngữ lập trình đều hỗ trợ. Hi vọng rằng bạn đã hiểu về kiểu dữ liệu này và sẽ sử dụng một cách hiệu quả trong công việc lập trình của mình.