Điều kiện quan hệ nhỏ hơn của nút con so với nút cha có thể được quy định trước tuỳ theo bài toán, không nhất thiết phải là nhỏ hơn theo nghĩa toán học, ngay cả quan hệ "nút A giá trị A>giá trị B" cũng hoàn toàn đúng. VD: Mặc dù được mô tả như 1 cây nhưng Heap lại có thể lưu trữ trong mảng, nút gốc là nút 1, nút con của nút I là 2 nút 2*I và 2*I+1. Đặc điểm của Heap: - Nút gốc luôn là nút lớn nhất [theo định nghĩa có trước] - Độ cao của 1 nút luôn nhỏ hơn hoặc bằng O(logN) vì cây heap cân bằng.  Ứng dụng chủ yếu của heap là chỉ tìm min, max trong 1 tập hợp động, nghĩa là tập có thể thay đổi, thêm, bớt các phần tử. (nhưng như vậy đã là quá đủJ) Các thao tác thường dùng trong xử lý HEAP: -Up_heap: nếu 1 nút lớn hơn cha của nó thì di chuyển nó lên trên -Down_heap: nếu 1 phần tử nhỏ hơn 1 con của nó thì di chuyển nó xuống dưới -Push: đưa 1 phần tử vào HEAP bằng cách thêm 1 nút vào cây và up_heap nút đó -Pop: loại 1 phần tử khỏi HEAP bằng cách chuyển nó xuống cuối heap và loại bỏ, sau đó chỉnh sửa lại heap sao cho thoả mãn các điều kiện của HEAP. Sau đây là Code minh hoạ: biến top là số phần tử của heap, A là mảng chứa heap, doicho(i,j) là thủ tục đổi chỗ 2 phần tử i và j của heap. procedure Up_heap(i:longint); begin if (i=1) or (a[i]>a[i div 2]) then exit; {i div 2 là nút cha của i} doicho(i,i div 2);{đổi chỗ 2 phần tử} up_heap(i div 2); end; procedure down_heap(i:longint); begin j:=i*2; if j>top then exit; if (ja[j-1]) then j:=j+1; {chọn nút lớn hơn trong 2 nút con} doicho(i,j); down_heap(j); end; procedure push(giatri:longint); begin inc(top); a[top]:=giatri;{mở rộng và thêm 1 phần tử vào tập} up_heap(top);{chỉnh lại heap cho thoả mãn điều kiện} end; procedure pop(vitri:longint); begin a[vitri]:=a[top]; dec(top);{loại 1 phần tử ra khỏi heap} {chỉnh lại heap, nếu phần tử bị loại luôn ở đầu heap có thể bỏ up_heap} up_heap(vitri); down_heap(vitri); end; 1 điểm đặc biệt lưu ý là trong quá trình đưa 1 phần tử ra khỏi heap tại vị trí bất kì phải thực hiện cả 2 quá trình up_heap và down_heap để đảm bảo Heap vẫn thoả mãn điều kiện đã cho. Qua đoạn chương trình ta có thể thấy được các điều kiện của HEAP vẫn được bảo tồn sau khi tập bị thay đổi. Heap được sử dụng trong thuật toán Dijkstra, Kruskal, Heap Sort nhằm giảm độ phức tạp thuật toán. Heap còn có thể sử dụng trong các bài toán dãy số, QHĐ, đồ thị... Với những ví dụ sau ta sẽ thấy phần nào sự đa dạng và linh hoạt trong sử dụng Heap. Để thuận tiện ta gọi Heap-max là heap mà giá trị nút cha lớn hơn giá trị nút con (phần tử đạt max là gốc của Heap) và Heap-min là heap mà giá trị nút cha nhỏ hơn giá trị nút con (phần tử đạt min là gốc của heap). Bài toán 1: MEDIAN (phần tử trung vị). Đề bài: Phần tử trung vị của 1 tập N phần tử là phần tử có giá trị đứng thứ N div 2+1 với N lẻ và N div 2 hoặc N div 2+1 với N chẵn. Cho 1 tập hợp ban đầu rỗng. Trong file Input có M<=10000 thao tác thuộc 2 loại: 1. PUSH gtr đưa 1 phần tử giá trị gtr vào trong HEAP (gtr<=10^9). 2. MEDIANtrả về giá trị của phần tử trung vị của tập hợp đó (nếu N chẵn trả về cả 2 giá trị). Yêu cầu: viết chương trình đưa ra file OUTPUT tương ứng. Input: dòng đầu tiên ghi số M, M dòng tiếp theo ghi 1 trong 2 thao tác theo định dạng trên. Output: tương ứng với mỗi thao tác MEDIAN trả về 1 (hoặc 2) giá trị tương ứng. Thuật giải: Dùng 2 heap, 1 heap (HA) lưu các phần tử từ thứ 1 tới N div 2 và heap còn lại (HB) lưu các phần tử từ N div 2 +1 tới N sau khi đã sort lại tập thành tăng dần. HA là Heap-max còn HB là Heap-min. Như vậy phần tử trung vị luôn là gốc HB (N lẻ) hoặc gốc của cả HA và HB (n chẵn). Thao tác MEDIAN do đó chỉ có độ phức tạp O(1). Còn thao tác PUSH sẽ được làm trong O(logN) như sau: - Nếu gtr đưa vào nhỏ hơn hoặc bằng HA[1] đưa vào HA ngược lại đưa vào HB. Số phần tử N của tập tăng lên 1. - Nếu HA có lớn hơn (/nhỏ hơn N) div 2 phần tử thì POP 1 phần tử từ HA (/HB) đưa vào heap còn lại. Sau quá trình trên thì HA và HB vẫn đảm bảo đúng theo định nghĩa ban đầu. Bài toán được giải quyết với độ phức tạp O(MlogM). Bài toán 2: Lazy programmer – NEERC western subregion QF 2004. Tóm tắt đề bài: Có N công việc buộc phải hoàn thành trước thời gian D[i] (thời gian hiện tại là 0). N công việc này được giao cho 1 programmer lười biếng. Xét 1 công việc I, bình thường programmer này làm xong trong B[i] thời gian nhưng nếu được trả thêm c($) thì sẽ làm xong trong B[i]-c*A[i] (nếu c=B[i]/A[i] thì anh ta có thể làm xong ngay tức khắc, t=0). Tất nhiên c<=B[i]/A[i]. Tiền trả thêm này với từng công việc là độc lập với nhau. Yêu cầu: với các mảng D[], B[] và A[] cho trước tìm số tiền ít nhất phải trả thêm cho programmer để mọi công việc đều hoàn thành đúng hạn. Input: Dòng đầu tiên ghi số N. Dòng thứ I trong N dòng tiếp theo mỗi dòng ghi 3 số lần lượt là A[i], B[i] và D[i]. Output: tổng số tiền nhỏ nhất phải trả thêm (chính xác tới 2 c/s thập phân). Giới hạn: N<=10^5, 1<=A[i],B[i]<=10^4, 1<=D[i]<=10^9. Thuật giải: Nhận thấy nếu xét tới thời điểm T thì mọi công việc có D[i] Từ đó ta có thuật giải sau: 1. Sắp xếp tăng dần các công việc theo các giá trị D[] của chúng 2. Dùng 1 Heap-max lưu các công việc theo giá trị A[], 1 mảng C để lưu số tiền còn có thể trả thêm cho các công việc. Khởi tạo C[i]=B[i]/A[i]. Khi xét tới công việc I thì đưa I vào Heap. Khởi tạo tien=0; Giả sử tới công việc I thì không hoàn thành được trước D[i], cần trả thêm tiền để các công việc từ 1 tới I đều được hoàn thành đúng hạn. Ta chỉ cần trả thêm sao cho I được hoàn thành đúng D[i], giả sử đó là T. Chọn công việc đứng đầu trong heap – có A[] đạt max, giả sử là j. Lưu ý thời gian làm 1 công việc luôn dương. Có các trường hợp xảy ra là: - C[j]*A[j]>T: C[j]-=T/A[j]; tien+=T/A[j];kết thúc xử lý công việc I. - C[j]*A[j]=T: loại bỏ j ra khỏi heap; tien+=C[j];kết thúc;{thời gian làm j đã = 0} - C[j]*A[j] Kết quả của bài toán chính là “tien”. Công việc trên kết thúc với T=0 nên công việc I đã được hoàn thành đúng hạn. Mọi công việc trước I đều đã hoàn thành đúng hạn nay hoặc giữ nguyên thời gian làm hoặc được trả thêm tiền làm nên cũng luôn hoàn thành đúng hạn. Vì ta luôn chọn A[] tối ưu nên số tiền phải trả cũng tối ưu. Nhờ sử dụng Heap nên độ phức tạp của thuật toán là O(NlogN) (do mỗi công việc vào và ra khỏi Heap không quá 1 lần). Bài toán 3: Connection - 10th polish olimpiad in informatics, stage II. Tóm tắt đề bài: Cho 1 đồ thị vô hướng gồm N đỉnh và M cung. 1 đường đi từ a tới b là đường đi đi qua các cung của đồ thị, có thể lặp lại các cung và đỉnh đã đi qua nhiều lần. Cần tìm độ dài đường đi ngắn thứ k từ a tới b cho trước. Yêu cầu: gồm 1 số câu hỏi, mỗi câu hỏi dạng a b k phải trả về giá trị đường đi ngắn thứ k từ a tới b. Input: Dòng đầu tiên ghi 2 số N M. Dòng thứ I trong M dòng tiếp theo mỗi dòng ghi 3 số “a b l” mô tả cung thứ I của đồ thị là cung từ a tới b có độ dài l. Dòng thứ M+2 chứa T là số câu hỏi. Trong T dòng tiếp theo mỗi dòng ghi 3 số “a b k” mô tả 1 câu hỏi. Các số trong input là số nguyên. Output: T dòng, dòng thứ I là câu trả lời cho câu hỏi thứ I. Giới hạn: N<=100, M<=N^2-N (đồ thị không có cung nào từ a tới a, có không quá 1 cung từ a tới b bất kì), 1<=k<=100, 04 kết quả = -1. Gợi ý thuật giải: Rõ ràng ta phải tính trước maxk=100 đường đi ngắn nhất từ a tới b. Làm sao để làm được điều đó? Với 1 đỉnh dùng thuật toán DIJKSTRA để tính maxk đường đi ngắn nhất tới tất cả các đỉnh còn lại. Giả sử đang xét tới đỉnh U, C[u,v,k] là đường đi ngắn thứ k từ u tới v. Với mỗi V <> U tính C[u,v,k] lần lượt với k từ 1 tới maxk (tính xong giá trị cũ rồi mới tính tới giá trị mới), k0[v] là giá trị k đang được tính của v (khởi tạo k0[v]=1). Sau đây là các bước cơ bản của thuật toán: CONNECTION(U) 1. Với v=1..N, v<>u: Tìm v: C[u,v,k0[v]] đạt GTNN, min=C[u,v,k0[v]]. 2. Xác nhận C[u,v,k0[v]] là đường cần tìm, K0[v]++. 3. Với các v’ mà có đường từ v tới v’ (dài L) tạo thêm 1 đường từ u tới v’ độ dài L’=min+L, cập nhật đường đi từ U tới V. End; Các bước 1 và 3 là của thuật toán Dijkstra thông thường. Vì các giá trị min chỉ được xét 1 lần nên với mọi đường đi mới từ U tới V’ ta đều phải lưu trữ lại, nhưng, do chỉ cần tìm maxk đường ngắn nhất nên ta cũng chỉ cần lưu trữ lại maxk-k0[v’] đường. bước 3 viết rõ ràng như sau: 3.Update(v’,L’) 3.1. Tìm đường dài nhất trong các đường đã lưu. 3.2. Nếu đường này ngắn hơn L’ kết thúc. 3.3. Loại bỏ đường này. 3.4. Lưu trữ đường dài L’. Tập các đường được lưu trữ với 1 đỉnh V là tập động, ta dùng 1 heap-max để lưu trữ tập các đường này. Lúc đó trong bước 1 thì C[u,v,k0[v]] phải chọn là min của tập trên. Có thể kết hợp 1 heap-min để tìm nhanh C[u,v,k0[v]]. Cách này cài đặt phức tạp và đòi hỏi phải hiểu rõ về heap. 1 cách khác đơn giản hơn là luôn cập nhật C[u,v,k0[v]] trong mỗi bước tìm được đường mới: 3.Update(v’,L’) 1.2.3.4 {các bước này như cũ} 5. Nếu (L’ C[u,v,k0[v]]=L’. Nhưng khi đó trong bước 2 của thuật toán ban đầu cần bổ sung như sau: 2.a/ Xác nhận..., K0[v]++. b/Nếu K0[v] Độ phức tạp của chương trình CONNECTION là O(N*K*logK). Phải gọi N lần chương trình này nên độ phức tạp của thuật toán là O(N^2*K*logK). Lưu ý không nên dùng thuật toán Dijkstra kết hợp cấu trúc heap trong bài toán này vì đồ thị đã cho là 1 đồ thị dày. Nhận xét: đây là 1 bài hay và khó ứng dụng heap, điểm quan trọng là nhận ra cách xây dựng lần lượt các đường ngắn nhất từ nhỏ tới lớn và ứng dụng heap vào trong quá trình này. Qua 1 vài ví dụ trên các bạn có thể thấy phần nào ứng dụng của heap đa dạng trong các bài toán như thế nào. Nhưng chắc không khỏi có bạn thốt lên “HEAP cũng chỉ có vậy, quá đơn giản, cứ tìm min/max thì dùng thôi”. Đó là do thuật giải đã được tôi nêu rất kĩ nên đơn giản, nhưng để nghĩ được ra cách ứng dụng heap không dễ dàng như vậy. 1 số bài toán luyện tập sau sẽ giúp các bạn hiểu rõ hơn: 1. Lightest language – POI VI, stage III. Cho trước 1 Tập Akgồm k chữ cái đầu tiên của bảng chữ cái (2<=k<=26). Mỗi chữ cái trong tập Ak có 1 khối lượng cho trước. Khối lượng của 1 từ bằng tổng khối lượng các chữ cái trong từ đó. 1 “language” của tập Ak là 1 tập hữu hạn các từ được xây dựng chỉ bởi các chữ cái trong tập A, có khối lượng bằng tổng khối lượng các từ thuộc nó. Ta nói 1 “language” là “prefixless” nếu như với mọi cặp từ u,v trong “language” đó thì u không là tiền tố của v (u là tiền tố của v nếu tồn tại s sao cho v=u+s với ‘+’ là phép hợp xâu). Yêu cầu: Tìm khối lượng nhỏ nhất có thể của 1 “language” gồm đúng N từ và là 1 “prefixless” của tập Ak cho trước. (N<=10000). Input: Dòng đầu tiên ghi 2 số N và K. Trong K dòng tiếp theo mỗi dòng ghi khối lượng của mỗi chữ cái trong tập Ak, theo thứ tự từ điển bắt đầu từ “a”. Output: Duy nhất 1 dòng ghi ra khối lượng nhỏ nhất có thể của 1 ngôn ngữ thoả những điều kiện trên. Ví dụ: Input 3 2 2 5 Output 16 (với input trên, ngôn ngữ được chọn là L={ab,aba,b} 2. Promotion - VII Polish Olympiad In Informatics 2000, stage III Cho 1 tập hợp A gồm các số tự nhiên. Ban đầu tập A là tập rỗng. Trong N ngày, người ta lần lượt làm các công việc sau: a/ Thêm vào tập A 1 số các số tự nhiên. b/ Lưu lại hiệu giữa số lớn nhất và số nhỏ nhất của tập A. c/ Loại bỏ 2 số lớn nhất và nhỏ nhất ra khỏi tập A. Yêu cầu: cho biết danh sách các số được thêm vào mỗi ngày, tính tổng các số được lưu lại sau mỗi ngày. Biết trong tập A trước bước b luôn có ít nhất 2 số. Input: Dòng đầu tiên ghi số N. Trong N dòng tiếp theo, mỗi dòng ghi theo định dạng sau: số đầu tiên là số lượng số được thêm vào, sau đó lần lượt là giá trị các số được thêm vào. Output: 1 số duy nhất là tổng các số được lưu lại VD: Input: 5 3 1 2 3 2 1 1 4 10 5 5 1 0 1 2 Output: 19 Gợi ý: 1 heap-min và 1 heap-max của cùng 1 tập động, cái khó của bài toán nằm trong kĩ năng cài đặt 2 heap của cùng 1 tập. Ngoài dùng heap có thể dùng Interval Tree hoặc Binary Indexed Tree. 3. BirthDay – thi vòng 2 TH, dựa trên bài thi IOI 2005. SN Byteman đã tới! Cậu đã mời được N-1 người bạn của mình tới dự tiệc SN. Cha mẹ cậu cũng đã chuẩn bị 1 cái bàn tròn lớn dành cho N đứa trẻ. Cha mẹ của Byteman cũng biết 1 số đứa trẻ sẽ gây ồn ào, ầm ĩ nếu chúng ngồi cạnh nhau. Do đó, những đứa trẻ cần được sắp xếp lại. Bắt đầu từ Byteman, bọn trẻ được đánh số từ 1 tới N. Thứ tự mới của chúng là 1 hoán vị (p1,p2,..pn) của N số tự nhiên đầu tiên – nghĩa là sau khi xếp lại đứa trẻ p(i) ngồi giữa đứa trẻ p(i-1) và đứa trẻ p(i+1), đứa trẻ p(n) ngồi cạnh đứa trẻ p(1) và p(n-1). Để xếp lại, 1 đứa trẻ cần di chuyển 1 số bước qua trái hoặc qua phải về vị trí phù hợp. Cha mẹ của byteman muốn những đứa trẻ di chuyển càng ít càng tốt - tức là tổng độ dài di chuyển của N đứa trẻ đạt GTNN. Tìm giá trị này. Input: Dòng đầu ghi số N, dòng tiếp theo ghi N số là thứ tự mới của bọn trẻ Output: số bước di chuyển ít nhất thoả mãn VD: Input: 5 1 5 4 3 2 Output: 6 Ngoài HEAP ra còn có 1 số loại Priority Queue khác như Biominal Heap Priority Queue hay Fibonacci heap... nhưng rất phức tạp, các bạn có thể tìm hiểu thêm ở các tài liệu khác.
School@net (Theo THNT)
|
Tìm kiếm
Khách: 11
Thành viên: 0
Tổng cộng: 11
