Hàng ưu tiên (priority queue)

Khái niệm hàng ưu tiên

Hàng ưu tiên là một kiểu dữ liệu trừu tượng tập hợp đặc biệt, trong đó mỗi phần tử có một độ ưu tiên nào đó.

Độ ưu tiên của phần tử thường là một số, theo đó, phần tử có độ ưu tiên nhỏ nhất sẽ được ‘ưu tiên’ nhất. Một cách tổng quát thì độ ưu tiên của một phần tử là một phần tử thuộc tập hợp được xếp theo thứ tự tuyến tính.

Trên hàng ưu tiên chúng ta chỉ quan tâm đến các phép toán: MAKENULL để tạo ra một hàng rỗng, INSERT để thêm phần tử vào hàng ưu tiên và DELETEMIN để xoá phần tử ra khỏi hàng với phần tử được xóa có độ ưu tiên bé nhất.

Ví dụ tại bệnh viện, các bệnh nhân xếp hàng để chờ phục vụ nhưng không phải người đến trước thì được phục vụ trước mà họ có độ ưu tiên theo tình trạng khẩn cấp của bệnh.

Cài đặt hàng ưu tiên

Chúng ta có thể cài đặt hàng ưu tiên bằng danh sách liên kết, danh sách liên kết có thể dùng có thứ tự hoặc không có thứ tự. Nếu danh sách liên kết có thứ tự thì ta có thể dễ dàng tìm phần tử nhỏ nhất, đó là phần tử đầu tiên, nhưng phép thêm vào đòi hỏi ta phải duyệt trung bình phân nửa danh sách để có một chổ xen thích hợp. Nếu danh sách chưa có thứ tự thì phép thêm vào có thể thêm vào ngay đầu danh sách, nhưng để tìm kiếm phần tử nhỏ nhất thì ta cũng phải duyệt trung bình phân nửa danh sách.

Ta không thể cài đặt hàng ưu tiên bằng bảng băm vì bảng băm không thuận lợi trong việc tìm kiếm phần tử nhỏ nhất. Một cách cài đặt hàng ưu tiên khá thuận lợi đó là cài đặt bằng cây có thứ tự từng phần.

Cài đặt hàng ưu tiên bằng cây có thứ tự từng phần

Định nghĩa cây có thứ tự từng phần

Cây có thứ tự từng phần là cây nhị phân mà giá trị tại mỗi nút đều nhỏ hơn hoặc bằng giá trị của hai con.

Ví dụ:

Hình IV.3: Cây có thứ tự từng phần

Nhận xét: Trên cây có thứ tự từng phần, nút gốc là nút có giá trị nhỏ nhất.

Từ nhận xét này, ta thấy có thể sử dụng cây có thứ tự từng phần đề cài đặt hàng ưu tiên và trong đó mỗi phần tử được biểu diễn bởi một nút trên cây mà độ ưu tiên của phần tử là giá trị của nút.

Để việc cài đặt được hiệu quả, ta phải cố gắng sao cho cây tương đối ‘cân bằng’. Nghĩa là mọi nút trung gian (trừ nút là cha của nút lá) đều có hai con; Đối với các nút cha của nút là có thể chỉ có một con và trong trường hợp đó ta quy ước là con trái (không có con phải).

Để thực hiện DELETEMIN ta chỉ việc trả ra nút gốc của cây và loại bỏ nút này. Tuy nhiên nếu loại bỏ nút này ta phải xây dựng lại cây với yêu cầu là cây phải có thứ tự từng phần và phải "cân bằng".

Chiến lược xây dựng lại cây như sau

Lấy nút lá tại mức cao nhất và nằm bên phải nhất thay thế cho nút gốc, như vậy cây vẫn "cân bằng" nhưng nó không còn đảm bảo tính thứ tự từng phần. Như vậy để xây dựng lại cây từng phần ta thực hiện việc "đẩy nút này xuống dưới" tức là ta đổi chổ nó với nút con nhỏ nhất của nó, nếu nút con này có độ ưu tiên nhỏ hơn nó.

Giải thuật đẩy nút xuống như sau:

• Nếu giá trị của nút gốc lớn hơn giá trị con trái và giá trị con trái lớn hơn hoặc bằng giá trị con phải thì đẩy xuống bên trái. (Hoán đổi giá trị của nút gốc và con trái cho nhau)
• Nếu giá trị của nút gốc lớn hơn giá trị con phải và giá trị con phải nhỏ hơn giá trị con trái thì đẩy xuống bên phải. (Hoán đổi giá trị của nút gốc và con phải cho nhau)
• Sau khi đẩy nút gốc xuống một con nào đó (trái hoặc phải) thì phải tiếp tục xét con đó xem có phải dẩy xuống nữa hay không. Quá trình đẩy xuống này sẽ kết thúc khi ta đã đẩy đến nút lá hoặc cây thỏa mãn tính chất có thứ tự từng phần.

Ví dụ: thực hiện DELETEMIN với cây trong hình IV.3 trên ta loại bỏ nút 3 và thay nó bằng nút 9 (nút con của nút 8 ), cây có dạng sau

Ta "đẩy nút 9 tại gốc xuống" nghĩa là ta đổi chỗ nó với nút 5

Tiếp tục "đẩy nút 9 xuống" bằng cách đổi chổ nó với 6

Quá trình đã kết thúc.

Xét phép toán INSERT, để thêm một phần tử vào cây ta bắt đầu bằng việc tạo một nút mới là lá nằm ở mức cao nhất và ngay bên phải các lá đang có mặt trên mức này. Nếu tất cả các lá ở mức cao nhất đều đang có mặt thì ta thêm nút mới vào bên trái nhất ở mức mới. Tiếp đó ta cho nút này "nổi dần lên" bằng cách đổi chổ nó với nút cha của nó nếu nút cha có độ ưu tiên lớn hơn. Quá trình nổi dần lên cũng là quá trình đệ quy. Quá trình đó sẽ dừng khi đã nổi lên đến nút gốc hoặc cây thỏa mãn tính chất có thứ tự từng phần.

Ví dụ: thêm nút 4 vào cây trong hình IV.3, ta đặt 4 vào lá ở mức cao nhất và ngay bên phải các lá đang có mặt trên mức này ta được cây

Cho 4 "nổi lên" bằng cách đổi chổ với nút cha

Tiếp tục cho 4 nổi lên ta có cây

Quá trình đã kết thúc

Cài đặt cây có thứ tự từng phần bằng mảng.

Trong thực tế các cây có thứ tự từng phần như đã bàn bạc ở trên thường được cài đặt bằng mảng hơn là cài đặt bằng con trỏ. Cây có thứ tự từng phần được biểu diễn bằng mảng như vậy gọi là HEAP. Nếu cây có n nút thì ta chứa n nút này vào n ô đầu của mảng A nào đó, A[1] chứa gốc cây. Nút A[i] sẽ có con trái là A[2i] và con phải là A[2i+1]. Việc biểu diễn này đảm bảo tính ‘cân bằng’ như chúng ta đã mô tả trên.

Ví dụ: HEAP có 15 phần tử ta sẽ có cây như trong hình IV.4

Hình IV.4

Nói cách khác nút cha của nút A[i] là A[i div 2], với i>1. Như vậy cây được xây dựng lớn lên từ mức này đến mức khác bắt đầu từ đỉnh (gốc) và tại mỗi mức cây phát triển từ trái sang phải. Cài đặt hàng ưu tiên bằng mảng như sau:

Khai báo

#define MaxLength 100

typedef int ElementType;

typedef int Position;

typedef struct

{

ElementType Data[MaxLength];

Position Last;

} PriorityQueue;

Khởi tạo hàng ưu tiên rỗng

void MakeNullPriorityQueue(PriorityQueue *L)

{

(*L).Last=0;

}

Thêm một phần tử vào hàng ưu tiên hay thêm một nút vào cây có thứ tự từng phần

void InsertPriorityQueue(ElementType X, PriorityQueue *L)

{

Position P;

ElementType temp;

if (FullPriorityQueue(*L))

printf("Hang day");

else

{

Position i=++L->Last;

L->Data[L->Last]=X;

while ((i>0)&&(p(L->Data[i])<p(L->Data[i/2])))

{

temp=(*L).Data[i];

(*L).Data[i]=(*)L.Data[i/2];

(*L).Data[i/2]=temp;

i=i/2;

}

}

}

Xóa phần tử có độ ưu tiên bé nhất

ElementType DeleteMin(Position P,PriorityQueue *L)

{

if (EmptyPriorityQueue(*L))

printf(" Hang rong!");

else

{

ElementType minimum= (*L).Data[1];

(*L).Data[1]=(*L).Data[(*L).Last];

(*L).Last--;

// Qua trinh day xuong

int i=1,found =0;

while ((i<=L->Last/2)&&(found==0))

// Tim nut be nhat trong hai nut con cua i

if((p((*L).Data[2*i]<p((*L).Data[2*i+1]))||(2*i==L->Last))

j=2*i;

else j=2*i+1;

if ((p((*L).Data[i]>p((*L).Data[j]))

{

// Doi cho hai phan tu

temp=(*L).Data[i];

(*L).Data[i]=(*L).Data[j];

(*L).Data[j]=temp;

i=j; // Bat dau o muc moi

}

else found=1;

return minimum;

}

}