Hàng Đợi Ưu Tiên C++

1. Khái niệm sản phẩm ưu tiên

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

Bạn đang xem: Hàng đợi ưu tiên c++


Độ ưu tiên của bộ phận thường là một trong những số, theo đó, thành phần có độ ưu tiên nhỏ nhất sẽ tiến hành ‘ưu tiên’ nhất. Một cách tổng quát thì độ ưu tiên của 1 phần tử là một trong những phần tử ở trong tập thích hợp được xếp theo vật dụng tự đường tính.Trên mặt hàng ưu tiên họ chỉ lưu ý đến các phép toán: MAKENULL để tạo nên một sản phẩm rỗng, INSERT nhằm thêm phần tử vào mặt hàng ưu tiên với DELETEMIN nhằm xoá bộ phận ra khỏi mặt hàng với thành phần được xóa bao gồm độ ưu tiên bé nhỏ nhất.Ví dụ tại dịch viện, những bệnh nhân xếp hàng để chờ giao hàng nhưng không hẳn người mang lại trước thì được giao hàng trước mà người ta có độ ưu tiên theo tình trạng cấp bách của bệnh.

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

Chúng ta tất 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 bao gồm thứ trường đoản cú hoặc không có thứ tự. Ví như danh sách links có trang bị tự thì ta hoàn toàn có thể dễ dàng tìm phần tử nhỏ dại nhất, đó là bộ phận đầu tiên, dẫu vậy phép thêm vào yên cầu ta nên duyệt vừa phải phân nửa danh sách để có một chổ xen đam mê hợp. Giả dụ danh sách chưa tồn tại thứ từ thì phép thêm vào có thể thêm vào ngay đầu danh sách, tuy thế để tra cứu kiếm phần tử nhỏ dại nhất thì ta cũng bắt buộc duyệt mức độ vừa phải phân nửa danh sách.Ta không thể cài đặt hàng ưu tiên bởi bảng băm vì chưng bảng băm không thuận tiện trong việc đào bới tìm kiếm kiếm phần tử bé dại nhất. Một cách thiết đặt hàng ưu tiên khá thuận lợi đó là cài đặt bằng cây bao gồm thứ từ bỏ từng phần.

Xem thêm: BáNh TráNg NướNg - Cách Làm Bánh Tráng Nướng Siêu Giòn Ngon Tại Nhà

a. Thiết đặt hàng ưu tiên bởi cây tất cả thứ từ bỏ từng phần

Định nghĩa cây gồm thứ từ bỏ từng phầnCây bao gồm thứ từ bỏ từng phần là cây nhị phân mà lại giá trị tại từng nút đều bé dại hơn hoặc bởi giá trị của nhì con.Ví dụ:Hình IV.3: Cây gồm thứ từ bỏ từng phần

Nhận xét: trên cây tất cả thứ trường đoản cú từng phần, nút cội là nút có mức giá trị nhỏ nhất.Từ dấn xét này, ta thấy rất có thể sử dụng cây tất cả thứ trường đoản cú từng phần đề cài đặt hàng ưu tiên và trong số đó mỗi phần tử được màn biểu diễn bởi một nút bên trên cây mà độ ưu tiên của phần tử là quý giá của nút.Để việc thiết lập được hiệu quả, ta phải cố gắng sao mang đến cây tương đối ‘cân bằng’. Nghĩa là phần lớn nút trung gian (trừ nút là cha của nút lá) đều có hai con; Đối với những nút phụ thân của nút là rất có thể chỉ bao gồm một bé và vào trường hợp kia ta quy ước là nhỏ trái (không bao gồm con phải).Để triển khai DELETEMIN ta chỉ việc trả ra nút nơi bắt đầu của cây và vứt bỏ nút này. Tuy vậy nếu sa thải nút này ta cần xây dựng lại cây với yêu ước là cây phải bao gồm thứ tự từng phần và nên "cân bằng".Chiến lược kiến thiết lại cây như sauLấy nút lá trên mức cao nhất và nằm cạnh sát phải nhất sửa chữa thay thế cho nút gốc, bởi thế cây vẫn "cân bằng" tuy vậy nó không còn đảm bảo tính máy tự từng phần. Bởi vậy để xây dừng lại cây từng phần ta triển khai việc "đẩy nút này xuống dưới" có nghĩa là ta thay đổi chổ nó cùng với nút con bé dại nhất của nó, nếu như nút con này còn có độ ưu tiên bé dại hơn nó.Giải thuật đẩy nút xuống như sau:
Nếu cực hiếm của nút gốc to hơn giá trị nhỏ trái cùng giá trị con trái to hơn hoặc bởi giá trị con buộc phải thì đẩy xuống mặt trái. (Hoán đổi quý hiếm của nút nơi bắt đầu và nhỏ trái mang lại nhau)Nếu giá trị của nút gốc lớn hơn giá trị con buộc phải và giá bán trị nhỏ phải nhỏ tuổi hơn giá chỉ trị con trái thì đẩy xuống bên phải. (Hoán đổi quý hiếm của nút nơi bắt đầu và con cần cho nhau)Sau lúc đẩy nút cội xuống một con nào đó (trái hoặc phải) thì phải liên 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ẽ chấm dứt khi ta đã đẩy mang đến nút lá hoặc cây thỏa mãn tính chất gồm thứ từ bỏ từng phần.Ví dụ: triển khai DELETEMIN cùng với cây trong hình IV.3 bên trên ta loại bỏ nút 3 và nỗ lực nó bởi nút 9 (nút con của nút 8 ), cây gồm dạng sau

Ta "đẩy nút 9 tại nơi bắt đầu xuống" tức thị ta đổi vị trí 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 6Quá trình vẫn kết thúc.Xét phép toán INSERT, nhằm thêm một phần tử vào cây ta bắt đầu bằng vấn đề tạo một nút new là lá nằm ở vị trí mức cao nhất và ngay mặt phải những lá đang xuất hiện trên nấc này. Nếu tất cả các lá sinh sống mức tối đa đều đang xuất hiện thì ta thêm nút mới vào bên trái nhất ở tại mức mới. Tiếp đó ta mang đến nút này "nổi dần dần lên" bằng cách đổi chổ nó cùng với nút thân phụ của nó nếu như nút cha có độ ưu tiên béo hơn. Quy trình nổi dần lên cũng là quy trình đệ quy. Quá trình đó vẫn dừng khi đang nổi lên đến nút nơi bắt đầu hoặc cây thỏa mãn nhu cầu tính chất gồm thứ trường đoản cú từng phần.

Xem thêm: Mua Lá Chè Xanh Mua Ở Đâu Tphcm, Lá Chè Xanh Tươi Tấn Phát Chống Lão Hóa Giá 80K

Ví dụ: thêm nút 4 vào cây trong hình IV.3, ta để 4 vào lá nghỉ ngơi mức cao nhất và ngay bên phải các lá đang xuất hiện trên mức này ta được câyCho 4 "nổi lên" bằng cách đổi chổ với nút cha
Tiếp tục đến 4 nổi lên ta bao gồm cây

Quá trình đang kết thúc2.2. Setup cây bao gồm thứ từ bỏ từng phần bởi mảng.Trong thực tế các cây gồm thứ trường đoản cú từng phần như đã bàn luận ở trên thường được setup bằng mảng rộng là thiết lập bằng bé trỏ. Cây có thứ từ bỏ từng phần được màn biểu diễn bằng mảng như vậy gọi là HEAP. Nếu cây gồm n nút thì ta đựng n nút này vào n ô đầu của mảng A như thế nào đó, A<1> chứa gốc cây. Nút A sẽ có được con trái là A<2i> cùng con cần là A<2i+1>. Việc màn biểu diễn này đảm bảo tính ‘cân bằng’ như chúng ta đã biểu đạt trên.Ví dụ: HEAP gồm 15 thành phần ta sẽ có cây như vào hình IV.4

Hình IV.4Nói phương pháp khác nút phụ vương của nút A là A, cùng với i>1. Bởi vậy cây được xây dựng phệ lên từ bỏ mức này đến hơn cả khác bước đầu từ đỉnh (gốc) với tại mỗi mức cây cách tân và phát triển từ trái sang phải. Thiết đặt hàng ưu tiên bởi mảng như sau:Khai báo
#define MaxLength 100typedef int ElementType;typedef int Position;typedef struct ElementType Data; Position Last; PriorityQueue;Khởi sinh sản hàng ưu tiên rỗngvoid MakeNullPriorityQueue(PriorityQueue *L) (*L).Last=0;Thêm 1 phần tử vào hàng ưu tiên tốt thêm một nút vào cây bao gồm thứ trường đoản cú 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->DataLast>=X; while ((i>0)&&(p(L->Data)Data))) temp=(*L).Data; (*L).Data=(*)L.Data; (*L).Data=temp; i=i/2;
Xóa phần tử có độ ưu tiên bé xíu nhấtElementType 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 ((iLast/2)&&(found==0)) // Tim nut be nhat trong hai nut con cua i if((p((*L).Data<2*i>Last)) j=2*i; else j=2*i+1; if ((p((*L).Data>p((*L).Data)) // Doi mang lại hai phan tu temp=(*L).Data; (*L).Data=(*L).Data; (*L).Data=temp; i=j; // Bat dau o muc moi else found=1; return minimum;
report this adCác khóa đào tạo qua video:Lập trình C Java C# SQL vps PHP HTML5-CSS3-JavaScript« Prev: lời giải và lập trình - C: IV. Tự điển (DICTIONARY)