MỤC LỤC
A. Phần mở đầu 1
I. Lý do chọn đề tài 1
II. Mục đích của đề tài 1
III. Nhiệm vụ và phương pháp nghiên cứu 1
VI. Điểm mới trong kết quả nghiên cứu 1
B. Nội dung 2
MỤC LỤC 1
Khái niệm 3
Các thao tác thường dùng đối với Heap Max 3
Khai báo 3
UpHeap 4
DownHeap 4
Push 6
Pop 6
Dijkstra Heap 6
Một số bài tập ứng dụng 8
1.Bài tập 1: Thả xốp 8
2. Bài tập 2: PILOT 10
3. Bài tập 3: Tiểu thuyết trinh thám 13
4.Bài tập 4: BASE3 17
Tài liệu tham khảo 21
A. PHẦN MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI
Công tác bồi dưỡng học sinh giỏi (HSG) là một công tác mũi nhọn trong việc nâng
cao chất lượng giáo dục, tạo nguồn lực, bồi dưỡng nhân tài cho nhà trường nói riêng, cho
địa phương nói chung. Bồi dưỡng HSG là một công việc khó khăn và lâu dài, đòi hỏi
nhiều công sức của thầy và trò.
Trong quá trình bồi dưỡng HSG môn Tin học ở bậc THPT thì cấu trúc dữ liệu heap
là cấu trúc dữ liệu đặc biệt quan trọng. Từ lí do trên, tôi xin trình bày sáng kiến kinh
nghiệm “CHUYÊN ĐỀ BỒI DƯỠNG HSG : CẤU TRÚC DỮ LIỆU HEAP VÀ ỨNG

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)
Các thao tác thường dùng đối với Heap Max
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.
3
Const
maxn = 100000;
Var
nHeap : LongInt;
Heap : array[0 maxn] of LongInt;
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:
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;
DownHeap
Nếu 1 nút nhỏ hơn nút con thì đẩy nó xuống dưới:
4
Procedure DownHeap(i : LongInt);
Var
j : LongInt;
Begin

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:
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
6
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:

• Dòng 1: Số nguyên dương N
• Dòng 2: N số nguyên dương
Kết quả: Ghi ra file văn bản SPONGE.OUT
• Ghi 1 số duy nhất là đáp án của bài toán
Ví dụ:
SPONGE.INP SPONGE.OUT
3
2 1 3
3
Thuật toán :
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.inp';
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]);

Begin
j := 2*i;
If (heap[j] > heap[j+1]) and (j <nheap) then inc(j);
If heap[i] > 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;

công.
Dữ liệu : Vào từ file văn bản PILOT.INP
• Dòng 1 : Số nguyên dương N, là số phi công ở HT airline.
• 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ụ.
Kết quả: Dữ liệu ra ghi vào file 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.
Hạn chế :
2
≤
N
≤
10000; N là số chẵn.
10
1
≤
a < c
≤
100.000
Ví dụ :
PILOT.INP PILOT.OUT PILOT.INP PILOT.OUT
6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000
32000 6

read(fi,a[i],b[i]);
close(fi);
end;
{* *}
procedure doicho(var x,y : longint);
var
tg : longint;
begin
tg := x;
11
x := y;
y := tg;
end;
{* *}
procedure upheap(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;
{* *}
procedure downheap(i : longint);
var
j : longint;
begin
j := 2 *i;
if j > nh then exit;

sum := sum + a[i];
push(a[i] - b[i]);
if i mod 2 = 1 then kq := kq + pop;
end;
end;
{* *}
procedure inkq;
12
begin
assign(fo,tfo);rewrite(fo);
write(fo,sum-kq);
close(fo);
end;
{* *}
BEGIN
nhap;
xuli;
inkq;
END.
3. Bài tập 3: Tiểu thuyết trinh thám
Ivan Đneprôp viết truyện tiểu thuyết trinh thám. Truyện của anh ta không có gì đặc
sắc: không có các tình huống ly kỳ đặc biệt, cũng không có các chi tiết hài hước tế nhị.
Thậm chí một hiệu sách đã bán các sáng tác của Ivan theo cân! Nhưng độc giả lại thích
truyện của Ivan. Nó dễ hiểu và giúp người ta thư giản sau một ngày lao động mệt nhọc.
Thực ra, bí mật sự thành công của Ivan là ở chổ không phải chính anh nghĩ ra các tình
huống mà là người em trai Alexei. Ivan có nhiệm vụ viết nó thành các bestsellers. Dĩ
nhiên hai anh em chia nhau hợp lý số tiền kiếm được. Điều đáng tiếc là khả năng sáng tạo
các tình huống ly kỳ của Alexei lại phụ thuộc vào chu kỳ sinh học của anh. Hai anh em
phân tích bảng chu kỳ sinh học của Alexei và thấy rằng trong thời gian tới Alexei sẽ nghĩ
được n chủ đề mới, chủ đề thứ i sẽ được nghĩ ra ở ngày r

Dữ liệu: Vào từ file văn bản PULP.INP:
• Dòng 1: Chứa số nguyên n (1 ≤ n ≤ 100.000),
• Mỗi dòng trong n dòng sau chứa 2 số nguyên r
i
và p
i
.
Kết quả: Ghi ra file PULP.OUT
• Một số nguyên – tổng thời gian ngắn nhất tìm được.
Ví dụ:
PULP.INP PULP.OUT
2
1 5
2 1
10
Thuật toán:
1. Sort tăng theo R[i]
2. Ví dụ với các thời điểm , dễ dàng ta thấy
3. Với mỗi khoảng thời gian t = R[i] – R[i-1], ta ưu tiên giải quyết công việc cần ít thời
gian nhất, giả sử là công việc P (Thấy ngay là sử dụng Heap để lấy công việc có thời
gian nhỏ nhất)
a. Nếu thời gian thực hiện công việc P < t thì thực hiện hết công việc P, thời
gian còn lại thực hiện tiếp các công việc có thời gian nhỏ tiếp theo.
b. Nếu thời gian thực hiện công việc P > 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 = 'pulp.inp';

procedure upheap(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;
{* *}
procedure downheap(i : longint);
var
j : longint;
begin
j := 2 * i;
if j > nh then exit;
if (j < nh) and (h[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;

else
begin
push(x-t);
t := 0;
end;
end;
push(p[i]);sum := r[i];
end;
while nh > 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)) do
dec(j);
if i <= j then

Yêu cầu:
Xác định số lượng nhỏ nhất các chữ số của N thỏa mãn tính chất đầu bài
Dữ liệu: BASE3.INP
Gồm 3 dòng, mỗi dòng là một số ở hệ cơ số 3.
Kết quả: BASE3.OUT
Số lượng chữ số nhỏ nhất của N. Nếu không tồn tại N thì ghi số 0.
Hạn chế
• Số chữ số của một số trong 3 số đầu bài cho trong khoảng từ 1 đến 16.000.
Ví dụ:
BASE3.INP BASE3.OUT
001
020
2020
13
Giải thích
N = 2020001001001 .
Time limit/test: 0.4
17
1 RL
Ký tự 1 ở giữa của xâu kết quả phải thuộc 1 trong 3 xâu:
Giả sử ký tự 1 của kết quả nằm ở vị trí I của xâu , ta sẽ xây dựng xâu kết quả
bằng cách thêm từng xâu vào trái hoặc phải (phần L là trái, ký tự 1 ở giữa, phần R là phải)
Ta sẽ xây dựng xâu đến khi thì dừng lại (yêu cầu đề bài)
Dễ thấy, ta chỉ quan tâm tới ghi nhận kết quả. Tức là nếu
tồn tại cách xây dựng L’, R’ mà
thỏa mãn cũng sử dụng cách xây dựng đó được với các cặp với
, chỉ cần lưu 1 cặp có
Quy hoạch động = cách xếp có với
Nếu mỗi lần ta luôn nắp xâu vào nửa ngắn hơn thì luôn đảm bảo
(do ). Với trạng thái , ta cập nhật cho trạng

ss := max(ss,len[i]) ;
end;
end;
procedure Upheap(i:longint) ;
var
x,y:longint ;
begin
x := h[i] ;
y := h2[i];
while (i > 1) and (d[x,y] < d[h[i div 2],h2[i div 2]]) do
begin
h[i] := h[i div 2] ;
h2[i] := h2[i div 2];
pos[h[i],h2[i]] := i ;
i := i div 2;
end ;
h[i] := x;
h2[i] := y;
pos[x,y] := i;
end;
procedure downheap(i:longint);
var
j,x,y:longint;
begin
x := h[i];
y := h2[i];
while i * 2 <= nh do
begin
j := i * 2 ;
if (j < nh) and (d[h[j],h2[j]] >d[h[j+1],h2[j+1]]) then

dec(nh);
downheap(1) ;
end;
procedure Update ;
var
i,j,k:longint;
begin
for i := 1 to 3 do
begin
if s[i][1] = '0' then k := 0 else k := 1;
j := xi + len[i];
if (j <= ss) and (d[j,k] > d[xi,yi] + len[i]) then
begin
d[j,k] := d[xi,yi] + len[i] ;
push(j,k) ;
end;
j := xi - len[i] ;
if (j >= -ss) and (d[j,yi] > d[xi,yi] + len[i]) then
begin
d[j,yi] := d[xi,yi] + len[i];
push(j,yi) ;
end ;
end;
end ;
procedure init;
var
i,j,k,u: longint;
begin
for i := -ss to ss do
for j := 0 to 1 do

Nhap;
init;
xuly;
close(fi);
close(fo) ;
end.
C. PHẦN KẾT LUẬN
Cấu trúc dữ liệu heap đóng vai trò hết sức quan trọng trong lập trình, 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(lgN). Học sinh hiểu được bản chất của cấu trúc dữ liệu heap sẽ giúp
cho học sinh yêu thích môn học và ham học hỏi, tìm tòi, sáng tạo.
Đề tài này đã mang tính thực tiễn rất cao, cụ thể là: đây là kiến thức rất quan trọng
trong quá trình bồi dưỡng học sinh giỏi.
Kết quả là có rất nhiều học sinh đã làm được các bài tập có ứng dụng của heap.
Tài liệu tham khảo
1. Giải thuật và lập trình – T.S Lê Minh Hoàng – ĐHSP Hà Nội
2. Website: www.infoarena.ro
XÁC NHẬN CỦA THỦ
TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 19 tháng 5 năm 2013
Tôi xin cam đoan đây là SKKN của mình viết,
không sao chép nội dung của người khác.
(Ký và ghi rõ họ tên)
Nguyễn Đặng Phú
21