Tài liệu Bồi dưỡng học sinh giỏi môn tin học chuyên đề cấu trúc dữ liệu heap

MỤC LỤC I. Khái niệm ......................................................................................................................... 2 II. Các thao tác thường dùng đối với Heap Max .............................................................. 2 1. Khai báo ............................................................................................................................2 2. UpHeap..............................................................................................................................2 3. DownHeap ........................................................................................................................3 4. Push....................................................................................................................................4 5. Pop .....................................................................................................................................4 6. Dijkstra Heap ....................................................................................................................5 III. Một số bài tập ứng dụng ................................................................................................. 6 1. Bài tập 1: Heapuri ............................................................................................................6 2. Bài tập 2: Thả xốp ............................................................................................................8 3. Bài tập 3: PILOT ........................................................................................................... 10 4. Bài tập 4: Tiểu thuyết trinh thám ................................................................................ 13 5. Bài tập 5: Cezar ............................................................................................................. 18 6. Bài tập 6: Toy Cars ....................................................................................................... 22 7. Bài tập 7: BASE3 .......................................................................................................... 26 IV. Một số bài tập vận dụng................................................................................................ 30 8. Bài tập 1: BOCSOI13 ................................................................................................... 30 9. Bài tập 2: Kế hoạch làm bài......................................................................................... 31 10. Bài tập 3: CATUN ........................................................................................................ 31 11. Bài tập 3: Barbar ........................................................................................................... 32 12. Bài tập 4: Cầu cảng ....................................................................................................... 33 13. Bài tập 5: K TỔNG BÉ NHẤT ................................................................................... 33 14. Bài tập 6: BINLADEN ................................................................................................. 34 BINLADEN.INP............................................................................................................................ 34 BINLADEN.OUT .......................................................................................................................... 34 V. Tài liệu tham khảo ......................................................................................................... 35 1 CHUYÊN ĐỀ: CẤU TRÚC DỮ LIỆU HEAP I. Khái niệm Heap là một trong những cấu trúc dữ liệu đặc biệt quan trọng, nó giúp ta có thể giải được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi làm việc với Heap là O(logN). Heap thực chất là một cây cân bằng thỏa mãn các điều kiện sau:  Một nút có không quá 2 nút con.  Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha của nó. Với Heap Min thì ngược lại. Mặc dù được mô tả như cây nhưng Heap có thể được biểu diễn bằng mảng. Nút con của nút i là 2*i và 2*i+1. Do Heap là cây cân bằng nên độ cao của 1 nút luôn <= logN. Ứng dụng chủ yếu của Heap là tìm Min, Max trong 1 tập hợp động (có thể thay đổi, thêm, bớt các phần tử) nhưng như vậy đã là quá đủ. (Mô hình biểu diễn Heap bằng cây nhị phân và bằng mảng) II. Các thao tác thường dùng đối với Heap Max 1. Khai báo Ở ví dụ này, Heap sẽ là mảng một chiều kiểu LongInt, nHeap là số phần tử của mảng. Const maxn = 100000; Var nHeap : LongInt; Heap : array[0..maxn] of LongInt; 2. UpHeap Nếu 1 nút lớn hơn nút cha của nó thì di chuyển nó lên trên: 2 Procedure UpHeap(i : LongInt); Begin if (i = 1) or (Heap[i] < Heap[i div 2]) then exit; // Nếu i là nút gốc hoặc nhỏ hơn nút cha thì không làm việc swap(Heap[i] , Heap[i div 2]); // Đổi chỗ 2 phần tử trong Heap; UpHeap(i div 2); // Tiếp tục di chuyển lên trên end; 3. DownHeap Nếu 1 nút nhỏ hơn nút con thì đẩy nó xuống dưới: 3 Procedure DownHeap(i : LongInt); Var j : LongInt; Begin j := i*2; if j > nHeap then exit; // Nếu i không có nút con thì không làm việc if (j < nHeap) and (Heap[j] < Heap[j+1]) then Inc(j); // Nếu i có 2 nút con thì chọn nút ưu tiên hơn if Heap[i] < Heap[j] then // Nếu nút cha nhỏ hơn nút con begin swap(Heap[i] , Heap[j]); // Đổi chỗ 2 phần tử trong Heap DownHeap(j); // Tiếp tục di chuyển xuống dưới end; end; 4. Push Đưa 1 phần tử mới vào Heap: Thêm 1 nút vào cuối Heap và tiến hành UpHeap từ đây: Procedure Push(x : LongInt); Begin Inc(nHeap); // Tăng số phần tử của Heap Heap[nHeap] := x; // Thêm x vào Heap UpHeap(nHeap); End; 5. Pop Rút ra 1 phần tử ở vị trí v trong Heap: Gán Heap[v] := Heap[nHeap] rồi tiến hành chỉnh lại Heap: Function Pop(v : LongInt) : LongInt; Begin Pop := Heap[v]; // Lấy phần tử ở vị trí v ra khỏi Heap Heap[v] := Heap[nHeap]; // Đưa phần tử ở cuối Heap vào vị trí v Dec(nHeap); // Giảm số phần tử của Heap đi 1 4 {Chỉnh lại Heap} UpHeap(v); DownHeap(v); End; Ngoài ra, khi sử dụng thuật toán Dijkstra/Prim kết hợp cấu trúc Heap, bạn còn có thể sử dụng cách Push và Pop khác thuận lợi hơn so với cách trình bày ở trên: 6. Dijkstra Heap 1/ Update – Dijkstra: Procedure Update(v : LongInt); // Đỉnh v vừa được sửa nhãn, cần chỉnh lại Heap var child , parent : LongInt; begin child := pos[v]; // child là vị trí của đỉnh v trong Heap if child = 0 then // Nếu đỉnh v chưa có trong Heap begin Inc(nHeap); // Tăng số phần tử của Heap child := nHeap; // Đưa v vào cuối Heap end; parent := child div 2; // parent là nút cha của child while (parent > 0) and (d[Heap[parent]] > d[v]) do // Nếu đỉnh ở nút parent kém ưu tiên hơn v thì bị “kéo xuống” nút child begin Heap[child] := Heap[parent]; // Đẩy đỉnh được lưu trong nút cha xuống nút con pos[Heap[child]] := child; // Ghi nhận lại vị trí mới của đỉnh đó child := parent; // Tiếp tục di chuyển lên parent := child div 2; end; Heap[child] := v; // Thao tác “kéo xuống” ở trên sẽ tạo ra 1 ô trống ở nút child để đặt v vào pos[v] := child; // Ghi nhận vị trí mới của đỉnh v trong Heap end; 2/ Pop – Dijkstra: Function Pop : LongInt; // Lấy từ Heap đỉnh có nhãn tự do nhỏ nhất var r , v , c : LongInt; begin Pop := Heap[1]; // Nút gốc là nút có nhãn tự do nhỏ nhất v := Heap[nHeap]; // v là đỉnh ở nút lá cuối Heap, sẽ được đảo lên đầu và vun đống Dec(nHeap); // Giảm số phần tử của Heap r := 1; // Bắt đầu từ nút gốc while r*2 <= nHeap do // Chừng nào r chưa phải là lá begin c := r*2; // c là nút con của r if (c d[Heap[c+1]]) then Inc(c); // Trong 2 nút con chọn nút con chứa đỉnh ưu tiên hơn if d[Heap[c]] >= d[v] then break; // Nếu v ưu tiên hơn thì không làm việc nữa Heap[r] := Heap[c]; // Chuyển đỉnh lưu ở nút con lên nút cha pos[Heap[r]] := r; // Cập nhật lại vị trí mới trong Heap của đỉnh đó r := c; // Tiếp tục di chuyển xuống dưới end; 5 Heap[r] := v; // Đỉnh v được đặt vào vị trí r để đảm bảo cấu trúc Heap pos[v] := r; // Ghi nhận vị trí mới của đỉnh v trong Heap end; Một số bài tập ứng dụng III. 1. Bài tập 1: Heapuri Cho danh sách gồm N phần tử. Chúng ta thực hiện một số thao tác trên danh sách. Có 3 loại thao tác sau : - Thao tác 1 : Cho phần tử x vào danh sách - Thao tác 2 : Xóa phần tử thứ t (theo thứ tự nhập vào) - Thao tác 3: Lấy ra phần tử nhỏ nhất trong danh sách Yêu cầu: Hãy cho biết các kết quả của thao tác 3 ? INPUT: HEAPURI.INP - Dòng 1: N - Các dòng tiếp theo là dãy thao tác cần xử lý theo định dạng 1 x, 2 x hoặc 3 tương ứng là thao tác 1, 2 và 3 OUTPUT : HEAPURI.OUT - Ghi trên nhiều dòng, mỗi dòng là kết quả của thao tác 3 theo thứ tự trong file input. Ví dụ : HEAPURI.INP HEAPURI.OUT 9 1 4 4 2 1 7 7 1 9 3 1 2 2 1 3 2 4 3 Dễ thấy đây là một danh sách động (số lượng phần tử thay đổi), vì vậy ta xây dựng một heapmin để lấy ra giá trị nhỏ nhất ở các thao tác 3. Để xóa phần tử thứ t theo thứ tự nhập vào thì ta lưu thêm một mảng Pos. #include #include #define maxn 200010 int N, L, NR; int A[maxn], Heap[maxn], Pos[maxn]; void push(int x) 6 { int aux; while (x/2 && A[Heap[x]]A[Heap[y*2]]) x = y*2; if (y*2+1<=L && A[Heap[x]]>A[Heap[y*2+1]]) x = y*2+1; aux = Heap[x]; Heap[x] = Heap[y]; Heap[y] = aux; Pos[Heap[x]] = x; Pos[Heap[y]] = y; } } intmain() { freopen("heapuri.in", "r", stdin); freopen("heapuri.out", "w", stdout); int i, x, cod; scanf("%d ", &N); assert(1<=N && N<=200000); for (i=1; i<=N; i++) { scanf("%d ", &cod); assert(1<=cod && cod<=3); if (cod < 3) 7 { scanf("%d ", &x); assert(1<=x && x<=1000000000); } if (cod == 1) { L++, NR++; A[NR] = x; Heap[L] = NR; Pos[NR] = L; push(L); } if (cod == 2) { A[x] = -1; assert(Pos[x] != 0); assert(1<=x && x<=NR); push(Pos[x]); Pos[Heap[1]] = 0; Heap[1] = Heap[L--]; Pos[Heap[1]] = 1; if (L>1) pop(1); } if (cod == 3) printf("%d\n", A[Heap[1]]); } return 0; } 2. Bài tập 2: Thả xốp Có N hạt xốp, hạt thứ i có khối lượng , được thả lần lượt xuống một ống nước đặc biệt được thiết kế sao cho tại mỗi thời điểm chỉ có một hạt xốp nhẹ nhất nổi lên trên bề mặt. Trước mỗi lần thả, hạt xốp đang nổi trên bề mặt sẽ bị ngấm nước và tăng gấp đôi khối lượng. Hỏi sau khi thả hạt xốp cuối cùng vào ống thì khối lượng xốp tăng so với tổng khối lượng ban đầu là bao nhiêu ? INPUT:SPONGE.INP - Dòng 1: Số nguyên dương N - Dòng 2: N số nguyên dương OUTPUT :SPONGE.OUT - Ghi 1 số duy nhất là đáp án của bài toán Ví dụ: 8 SPONGE.INP SPONGE.OUT 3 3 2 1 3 Tương tự bài 1, dễ thấy đây là một danh sách động (giá trị phần tử thay đổi), vì vậy ta xây dựng một heapmin để lấy ra hạt xốp nhỏ nhất, tăng gấp đôi khối lượng rồi cập nhật lại heapmin. COnst tfi='sponge.in'; tfo='sponge.out'; Type arr1=array[0..100001] of longint; Var fi,fo : text; w,heap,head,ke,d,c,dd,cost : arr1; n,nheap,delta : longint; {==================================} Procedure nhap; Var i :longint; Begin Assign(fi,tfi);Reset(fi); read(fi,n); For i := 1 to n do read(fi,w[i]); cost := w; Close(fi); End; {==================================} Procedure doicho(varx,y : longint); var tmp :longint; Begin tmp := x; x := y; y := tmp; End; {==================================} Procedure upheap(i : longint); Var j :longint; Begin While (i <> 1) and (heap[i] heap[j+1]) and (j heap[j] then Begin doicho(heap[i],heap[j]); i :=j; End else exit; End; End; {=============================} Procedure push(x :longint); Begin inc(nheap); heap[nheap] := x; upheap(nheap); End; {=============================} Procedure xuly; Var i1 :longint; Begin For i1 := 1 to n-1 do Begin push(w[i1]); delta := delta + heap[1]; heap[1] := heap[1]*2; downheap(1); End; End; {==================================} BEGIN Assign(fo,tfo);Rewrite(fo); nhap; xuly; write(fo,delta); Close(fo); END. 3. Bài tập 3 :PILOT HT AIRLINE là một hãng hàng không danh tiếng ở Việt Nam, tuy nhiên, để tồn tại trong cơn bão suy thoái kinh tế, Ban giám đốc quyết định giảm chi phi tiền lương cho phi công càng nhiều càng tốt. 10 HT airline có tất cả N phi công (N là số chẵn), các phi công được đánh số từ 1 đến N (Phi công 1 là phi công trẻ nhất, phi công i là phi công có tuổi cao thứ i,… phi công n là phi công cao tuổi nhất). HT airline cần chính xác N phi hành đoàn, mỗi phi hành đoàn 2 gồm 2 phi công (một lái chính và một lái phụ), lái chính phải nhiều tuổi hơn lái phụ. Hợp đồng mà công ty kí với các phi công có 2 điều khoản rõ ràng: tiền lương khi là lái chính và tiền lương khi là lái phụ. Rõ ràng, đối với 1 phi công, tiền lương lái chính bao giờ cũng cao hơn tiền lương khi lái phụ. Tuy nhiên, với một phi hành đoàn, có thể tiền lương của lái chính lại thấp hơn lái phụ. Để giảm chi phí trả tiền lương, HT phải xác định một cách phân chia tối ưu N phi 2 hành đoàn. Bạn hãy giúp HT viết chương trình xác định số tiền tối thiểu để trả lương cho N phi công. INPUT: PILOT.INP - Dòng 1 : Số nguyên dương N, là số phi công ở HT airline.(2  N  10000; N là số chẵn) - N dòng tiếp theo, dòng thứ i là thông tin về phi công i : gồm hai số a và c viết cách nhau 1 dấu cách trống, tương ứng là tiền lương khi lái chính và tiền lương khi lái phụ (1  a < c  100.000). OUTPUT: PILOT.OUT - Một số nguyên duy nhất là tiền lương tối thiểu phải trả cho N phi công. Ví dụ : PILOT.INP 6 10000 9000 6000 5000 9000 8000 PILOT.OUT 32000 7000 3000 4000 1000 3000 6000 PILOT.INP 6 5000 4000 9000 11000 7000 8000 PILOT.OUT 33000 3000 1000 7000 5000 3000 6000 Time limits / test: 1s Ta có nhận xét sau: Theo thứ tự i nhập vào từ 1 đến N, thì cứ i lẻ thì phải có 1 lái phụ. Vì vậy, ta xây dựng một heap max, lần lượt cho vào heap, khi i lẻ thì ta lấy trong heap ra một nút, đây chính là lái phụ. CONST tfi tfo max TYPE = = = 'pilot.inp'; 'pilot.out'; 100000; 11 Arr1 = array[1..max] of longint; VAR fi,fo : text; n,nh,sum,kq : longint; a,b,h : Arr1; {*--------------------------------------------------------------- --*} procedurenhap; var i : longint; begin assign(fi,tfi);reset(fi); read(fi,n); For i := 1 to n do read(fi,a[i],b[i]); close(fi); end; {*----------------------------------------------------------------- *} proceduredoicho(varx,y : longint); var tg : longint; begin tg := x; x := y; y := tg; end; {*----------------------------------------------------------------- *} procedureupheap(i : longint); begin if (i = 1) or (h[i] < h[i div 2]) then exit; if h[i div 2] < h[i] then begin doicho(h[i div 2],h[i]); upheap(i div 2); end; end; {*----------------------------------------------------------------- *} proceduredownheap(i : longint); var j : longint; begin j := 2 *i; if j >nh then exit; if (j t thì chúng ta thực hiện công việc P trong khoảng thời gian t, thời gian còn lại là t[P] – t ta lưu lại trong Heap để tính tiếp. 4. Sau khi xét đến thời điểm N, lúc này ta sẽ phải làm tất cả các công việc còn lại tuần tự từ nhỏ đến lớn, hay là lấy tất cả các phần tử trong Heap ra là xong. CONST tfi tfo max TYPE = = = 'pulp.inp'; 'pulp.out'; 100000; Arr1 = array[1..max] of longint; VAR fi,fo : text; n,nh,sum,res : longint; r,p,h : Arr1; {*------------------------------------------------------------*} procedurenhap; var i : longint; begin assign(fi,tfi);reset(fi); read(fi,n); For i := 1 to n do read(fi,r[i],p[i]); close(fi); end; {*------------------------------------------------------------*} proceduredoicho(varx,y : longint); var tg : longint; begin tg := x; x := y; y := tg; end; {*------------------------------------------------------------ *} procedureupheap(i : longint); begin if (i = 1) or (h[i] > h[i div 2]) then exit; if h[i div 2] > h[i] then begin doicho(h[i div 2],h[i]); upheap(i div 2); end; end; {*------------------------------------------------------------ *} proceduredownheap(i : longint); var 15 j : longint; begin j := 2 * i; if j >nh then exit; if (j h[j+1]) then inc(j); if h[i] > h[j] then begin doicho(h[i],h[j]); downheap(j); end; end; {*------------------------------------------------------------ *} procedure push(x : longint); begin inc(nh); h[nh] := x; upheap(nh); end; {*------------------------------------------------------------ *} function pop : longint; begin pop := h[1]; h[1] := h[nh]; dec(nh); downheap(1); end; {*------------------------------------------------------------ *} procedurexuli; var i,t,x : longint; begin nh := 0; push(p[1]); sum := r[1]; res := 0; For i := 2 to n do begin t := r[i] - r[i-1]; while (nh> 0) and (t > 0) do begin x := pop; if (x <= t) then begin t := t - x; sum := sum + x; res := res + sum; end else begin push(x-t); t := 0; 16 end; end; push(p[i]);sum := r[i]; end; whilenh> 0 do begin x := pop; sum := sum + x; res := res + sum; end; end; {*------------------------------------------------------------ *} procedure sort(x,y:longint); var i,j,key1,key2 : longint; begin i := x; j := y; key1 := r[x+random(y-x+1)]; key2 := p[x+random(y-x+1)]; repeat while (r[i] < key1) or ((r[i] = key1) and (p[i] < key2)) do inc(i); while (r[j] > key1) or ((r[j] = key1) and (p[j] > key2)) dodec(j); if i <= j then begin doicho(r[i],r[j]); doicho(p[i],p[j]); inc(i); dec(j); end; until i > j ; if x < j then sort(x,j); if y > i then sort(i,y); end; {*------------------------------------------------------------ *} {*------------------------------------------------------------ *} procedureinkq; begin assign(fo,tfo);rewrite(fo); write(fo,res); close(fo); end; {*------------------------------------------------------------ *} {*------------------------------------------------------------ *} {*------------------------------------------------------------ *} {*------------------------------------------------------------ *} BEGIN randomize; 17 nhap; sort(1,n); xuli; inkq; END. 5. Bài tập 5: Cezar Tại HT Land, có tất cả n thượng nghị sĩ ở trong n ngôi biệt thự (đánh số từ 1 đến n), giữa 2 ngôi nhà có một đường đi duy nhất: đường đi trực tiếp hoặc không trực tiếp (đi qua các con đường khác). Tất cả các ngôi nhà đều đi được đến nhau. Mỗi thượng nghị sĩ khi đi từ nhà mình đến thượng viện, phải trả 1 USD khi đi qua một con phố (phố = đường nối trực tiếp 2 nhà bất kỳ). HT – người đứng đầu thượng viện đã nghĩ cách làm sao cho số tiền mà các thượng nghĩ sĩ phải trả là tối thiểu. Vì vậy, HT quyết định  Có k con phố miễn phí (thượng nghị sĩ sẽ không phải trả tiền khi đi trên con phố này)  Đặt tòa nhà thượng viện ở một trong n ngôi nhà Bạn hãy viết chương trình tính xem chi phí tối thiểu là bao nhiêu? INPUT: CEZAR.INP - Dòng 1: Số nguyên n và k tương ứng là số ngôi nhà ở HT land và số đường phố miễn phí - N – 1 dòng tiếp theo, mỗi dòng chứa 2 số i j có nghĩa là có con phố nối ngôi nhà i và ngôi nhà j OUTPUT: CEZAR.OUT Chi phí tối thiểu phải trả Giới hạn:  Ví dụ CEZAR.INP 13 3 12 23 28 78 75 54 56 89 8 10 10 11 10 12 10 13 CEZAR.OUT Giải thích 6 3 1 4 5 11 Có nhiều phương án giải quyết: Đây là 1 phương án: – 5-7, 7-8, 8-10 là những đường miễn phí – 8 là thượng viện Chi phí tối thiểu là: 18 2 7 8 10 9 11 12 13 11. Time limit:0.5 s/test Thuật toán: 1. Chúng ta sẽ tìm con đường phải trả phí đi lại. 2. Khởi tạo D[i] = trọng số của đỉnh i với ý nghĩa = số lượng người đi đến thượng viện phải đi qua con đường này. Ban đầu 3. Tại mỗi bước chúng ta sẽ cho các nút lá vào Heap, mỗi lần lấy 1 phần tử trong heap chúng ta sẽ update lại trọng số của đỉnh kề với đỉnh vừa lấy ra và nếu đỉnh vừa update thành nút lá ta lại cho vào trong heap. Sau khi lấy xong đỉnh thì cập nhật đáp án. Const tfi='cezar.inp'; tfo='cezar.out'; oo = 1000000000; Type arr1=array[0..100000] of longint; arr2=array[0..100000] of boolean; arr3=array[0..15000] of longint; arr4=array[0..15000] of arr3; Var fi,fo : text; heap,head,ke,d,c,pos,cost,trace,deg : arr1; free : arr2; k,n,nheap,f,r,sum,res : longint; count : arr4; {===============================} Procedure nhap; Var i,u,v : longint; Begin Assign(fi,tfi);Reset(fi); read(fi,n,k); For i := 1 to n-1 do Begin read(fi,u,v); d[i] := u; c[i] := v; inc(deg[u]); inc(deg[v]); ENd; head[1] := deg[1]; For i := 2 to n+1 do Begin head[i] := head[i-1] + deg[i]; 19 End; For i := 1 to n-1 do Begin u := d[i]; v := c[i]; ke[head[u]] := v; ke[head[v]] := u; cost[head[u]] := 1; cost[head[v]] := 1; dec(head[u]); dec(head[v]); End; Close(fi); End; {===============================} Procedure khoitao; Var i :longint; Begin Fillchar(free,sizeof(free),true); For i := 1 to n do BEgin pos[i] := 0; cost[i] := 1; End; nheap := 0; End; {===============================} Procedure downheap(root : longint); Var child,u : longint; BEgin u := heap[root]; repeat child := root*2; If (child cost[heap[child+1]]) then inc(child); If (child >nheap) or (cost[heap[child]]>= cost[u]) then break; heap[root] := heap[child]; pos[heap[root]] := root; root := child; Until false; heap[root] := u; pos[u] := root; End; {===============================} Procedure upheap(child : longint); Var root,u : longint; Begin u := heap[child]; 20