Hàng đợi ưu tiên là gì?

Một hàng đợi ưu tiên là một kiểu dữ liệu trừu tượng (Abstract data type - ADT) nó hoạt động như một queue ngoại trừ việc mỗi phần tử trong queue có một độ ưu tiên nhất định. Độ ưu tiên của các phần tử trong PQ xác định thứ tự của nó khi được remove khỏi PQ.

Heap là gì?

Một heap là một kiểu dữ liệu tree thỏa mãn điều kiện của heap: Nếu A là node cha của node B, thì giá trị của A thuộc 1 trong 2 trường hợp:

• Giá trị của node cha lớn hơn tất cả giá trị của các node con cháu của A. (max-heap)
• Giá trị của node cha nhỏ hơn tất cả giá trị của các node con cháu của A. (min-heap)

Khi nào và ở đâu thì dùng PQ?

• Được dùng trong ứng dụng thuật toán đường đi ngắn nhất Dijkstra

• Bất cứ khi nào bạn cần lấy thằng 'to nhất' hoặc 'nhỏ nhất' trong mảng.

• Được sử dụng trong Huffman coding.

• BFS hoặc A* sử dụng PQ để lấy node mà có giá trị (to hoặc nhỏ nhất tiếp theo)

• Được sử dụng trong Minimum Spanning Tree.

Chuyển Min PQ thành Max PQ

Problem : Thường thì các thư viện mà chúng ta sử dụng chỉ cung cấp min PQ, nhưng thỉnh thoảng chúng ta cần Max PQ.

Khi các phần tử trong PQ có thể so sánh được thì chúng ta đơn giản chỉ cần đổi dấu các phần từ để thành max heap.

Các cách để cài đặt một Priority Queue

PQ thường được cài đặt với heaps vì nó cho kết quả time complexity tốt nhất

PQ là một ADT (kiểu dữ liệu trừu tượng), nên là ko chi có một cách để cài đặt PQ. Ví dụ ta cỏ thể dùng list (mảng) nhưng mà nó ko cho kết quả tốt như heap

PQ with binary heap

• Một binary heap là một cây nhị phân (binary tree) nó thỏa mản điều kiện của heap. Trong cây nhị phân thì các node chỉ có tối đa 2 node con.

• Một cây nhị phân hoàn toàn là 1 cây mà trong mỗi tầng (có thể ngoại trừ tầng cuối) thì đều được full node. Ví dụ có 4 tầng thì tầng 3 phải có đầy đủ node là 4 node. (Bạn vẽ ra thì hiểu)

Biểu diễn binary heap

Bằng mảng. Lấy i là node cha => 2i + 1 là node con trái. 2i + 2 là node con phải.

Source code

Parsing source code...