Hàng ưu tiên là một kiểu dữ liệu đặc biệt, được xây dựng từ cấu trúc hàng đợi (queue) nhưng chứa thêm giá trị key để đánh giá mức độ ưu tiên của một phần tử trong hàng.

Xây dựng hàng ưu tiên

Chúng ta có thể xây dựng hàng ưu tiên dựa trên cấu trúc thẳng hàng (linear) hoặc phân nhánh (non-linear). Đối với cấu trúc thẳng hàng, hàng ưu tiên có thể được cài xây dựng thông qua một mảng (array), danh sách liên kết (linked list) hoặc array-based binary heap. Đối với cấu trúc phân nhánh, chúng ta có thể xây dựng dựa trên cây tìm kiếm (Binary search tree) hoặc pointer-based binary heap.

 

    Array-based priority queue (Hàng ưu tiên dựa trên mảng)

 

Xây dựng hàng ưu tiên dựa trên mảng là cách làm dễ nhất. Giả sử chúng ta có các phần tử có key là 1, 3, 5, 6, 8. Khi thêm các phần tử đó vào hàng ưu tiên, chúng sẽ có thứ tự sau:





Giả sử khi phần tử đầu trong hàng bị xoá đi, các phần tử phía sau đó phải dịch sang trái 1 vị trí để đảm bảo giữ đúng kích thước mới của hàng và không tốn bộ nhớ. Tuy nhiên, khi đó hàm xoá sẽ có độ phức tạp O(n)




Thay vì dịch trái cách phần tử, chúng ta có thể giữ nguyên đó và tăng vị trí của phần tử đầu lên 1





Tuy nhiên cách làm này sẽ khiến cho các phần tử bị trôi (rightward drift) và phung phí bộ nhớ.

Đối với hàm thêm phần tử, độ phức tạp của nó sẽ là O(n) nếu như phần tử được thêm vào có vị trí đứng đầu, lúc này các phần tử trong mảng sẽ phải dịch chuyển sang phải 1 bước.

    Linked-based priority queue (Hàng ưu tiên dựa trên danh sách liên kết)

Cũng như phương pháp ở trên, hàm xoá phần tử của hàng ưu tiên cũng sẽ có độ phức tạp O(1) do chỉ phải xoá phần tử đầu tiên trong hàng.





Do sử dụng cấu trúc con trỏ để nối tới nhau, khi thêm 1 phần tử mới vào hàng, chúng ta có thể chêm nó vào giữa 2 phần tử khác. Tuy nhiên, việc sử dụng con trỏ sẽ khiến cho chúng ta không thể tiếp cận vị trí mới của phần tử ngay lập tức (do không có vị trí của phần tử trong mảng). Đối với trường hợp xấu nhất (phần tử có giá trị cao nhất), hàm xoá sẽ có độ phức tạp O(n).





    Hàng ưu tiên dựa trên cây tìm kiếm (BST-based priority queue)

Đối với cây tìm kiếm, các hàm thêm và xoá phần tử sẽ có độ phức tạp O(log(n)) nếu như cây cân bằng. Tuy nhiên trong trường hợp xấu nhất, các hàm trên sẽ có độ phức tạp O(n) do cây tìm kiếm sẽ có cấu trúc thẳng và trở thành một danh sách liên kết.





    Priority queue as pointer-based binary heap

Binary heap có cấu trúc tương tự cây tìm kiếm, tuy nhiên do cách sắp xếp vị trí của các nút con, binary heap đảm bảo sẽ tạo ra được cây cân bằng, giúp cho các hàm thêm và xoá có độ phức tạp O(log(n)). Sau khi thêm hoặc xoá một nút, binary heap sẽ trở thành semi-heap do có nút nằm ở sai vị trí. Để đảm bảo các thuộc tính của mình, kiểu dữ liệu trên sẽ phải tự điều chỉnh các nút con về đúng vị trí (gọi là Heapify hay Re-heap).





Giả sử chúng ta có cấu trúc binary heap như trên, khi thực hiện viêc xoá, nút 1 sẽ bị xoá đi, và 1 nút con sẽ được đưa vào vị trí của nút 1 (nút 4)





Để đảm bảo chính xác thuộc tính của binary heap trên (Trong trường hợp này sẽ là min binary heap - Nút con sẽ lớn hơn hoặc bằng nút cha). Nút số 4 sẽ so sánh với các nút con của mình và tìm ra nút có giá trị bé nhất và hoán đổi vị trí cho nhau





Sau khi hoán đổi, semi-heap trên đã trở lại thành một binary heap hoàn chỉnh. (Các nút con lớn hơn nút cha)





Tương tự với hàm xoá, giả sử chúng ta thêm vào binary heap trên 1 nút có giá trị là 1, nút đó sẽ được đưa vào cuối binary heap, sau đó nó sẽ trở thành semi heap và thực hiện re-heap để đưa các nút trở về đúng vị trí.





Heapify: so sánh nút mới được đưa vào (1) và nút cha (4), hoán đổi 1 và 4:




Tiếp tục so sánh nút 1 với nút cha (3), do có giá trị bé hơn, hoán đổi 2 nút trên





Sau khi hoán đổi 2 nút trên, semi-heap đã trở lại thành một binary heap hoàn chỉnh.

Có vẻ như xây dựng hàng ưu tiên dựa trên binary heap là một cách tốt nhất, tuy nhiên do việc sử dụng con trỏ, cách xây dựng trên sẽ có nhược điểm tốn bộ nhớ. Để khắc phục điểm yếu trên, chúng ta sẽ tìm tới một cách cài đặt tốt hơn: array-based binary heap (binary heap dựa trên mảng)





    Priority queue via array-based binary heap

Bây giờ chúng ta sẽ xem xét ví dụ binary heap vừa trên khi được đặt trong mảng.





Theo như hình trên, cấu trúc binary heap hoàn toàn có thể được cài đặt dựa trên kiểu mảng. Giả sử chúng ta có một binary heap A với nút cha có vị trí A, nút con bên trái sẽ có vị trí A[2*i] và nút con bên phải sẽ có giá trị A[(2*i)+1]. Cách cài đặt trên cũng đảm bảo không tốn quá nhiều dữ liệu do không cần sử dụng con trỏ.

    Nâng cao hiệu quả bằng bit manipulation


"Trên thế giới này có 10 kiểu người: những người hiểu mã nhị phân và những người không hiểu nó"


Thay vì sử dụng A[2*i] và A[(2*i)+1], chúng ta có thể sử dụng toán tử bit (trong trường hợp này sẽ dùng tới bitwise OR, bit shift right và bit shift left). Giả sử nút cha có vị trí là 2, các nút con sẽ có vị trí lần lượt là 4 và 5, các giá trị trên khi đưa về kiểu nhị phân sẽ trông như sau:







Để đưa giá trị 2 thành 4, chúng ta có thể dùng bit shift left (i << 1) (dịch chuyển sang trái 1 đơn vị)





Đối với giá trị 5, chúng ta thực hiện bit shift left và bitwise OR ((i >> 1) | 1)





Đính kèm trong bài viết là code cài đặt hàng đợi ưu tiên dựa trên binary heap được viết bằng Java dành cho các bạn nào muốn tìm hiểu thêm về cấu trúc dữ liệu này.

Login để lấy link download