Có thể nói Heap là 1 cấu trúc hữu dụng vào bậc nhất trong giải toán. Trong
khoa học máy tính, đống (tiếng Anh: heap) là một cấu trúc dữ liệu dựa trên cây thỏa
mãn tính chất đống: nếu B là nút con của A thì khóa(A)≥khóa(B) (HEAP MAX) .
Một hệ quả của tính chất này là khóa lớn nhất luôn nằm ở nút gốc. Do đó một đống
như vậy thường được gọi là đống-max. Nếu mọi phép so sánh bị đảo ngược khiến
cho khóa nhỏ nhất luôn nằm ở nút gốc thì đống đó gọi là đống-min. Thông thường
mỗi nút có không quá hai nút con. Mục đích của heap trong các bài các bài toán tin là
ta có thể truy xuất phần tử lớn nhất hay nhỏ nhất có trong một mảng lưu trữ hiện tại.
Do đó có 2 loại là heap_max và heap_min. Đống là một cách thực hiện kiểu dữ liệu
trừu tượng mang tên hàng đợi ưu tiên. Đống có vai trò quan trọng trong nhiều thuật
toán
Một số ứng dụng của Heap:
+ Heapsort: Một trong những phương pháp sắp xếp tại chỗ tốt nhất
+ Thuật toán lựa chọn: có thể sử dụng đống để tìm phần tử lớn nhất, nhỏ nhất, trung
vị, phần tử lớn thứ k, trong thời gian tuyến tính.
+ Thuật toán cho đồ thị: nhiều thuật toán cho đồ thị sử dụng cấu trúc dữ liệu đống
chẳng hạn như thuật toán Dijkstra, hay thuật toán Prim.
Các thao tác thường gặp trên đống là:
+ Tìm-max (tìm-min): tìm khóa lớn nhất trong đống-max (tìm khóa nhỏ nhất trong
đống-min).
+ Xóa-max (xóa-min): xóa nút gốc của đống-max (đống-min)
+ tăng-khóa (giảm-khóa): thay đổi giá trị một khóa trong đống-max (đống-min)
+ chèn: chèn thêm một khóa mới vào đống
+ hợp: hợp hai đống lại thành một đống mới chứa tất cả các khóa của cả hai
II. CẤU TRÚC HEAP
1
Heap được biểu diễn bằng cây nhị phân, nút k trên cây sẽ có hai nút con là 2*k
và 2*k+1, có cha là k div 2. Heap[k] tùy theo loại heap mà nó lớn hơn con nó hay cha
nó. Mỗi khi ta thay đổi một phần tử bất kì trong heap thì ta sẽ cập nhật lại heap trong
khoảng thời gian log n. Có hai thao tác đối với heap là upheap và downheap.
Heap sẽ cần biến nh để quản lí số lượng phần tử của heap.
Ví dụ với HEAP MAX
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 đó
– Del: 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.
Trong code x là vị trí, a là giá trị, nh là số phần tử, pa là cha của x, c là con của
x.
void upheap(int x)
{
if (x == 1) return; // x là gốc thì làm gì có cha
int pa = x/2; // cha của x
if(heap[x] > heap[pa]){ // x hơn cha nó nên đi lên
swap(heap[x],heap[pa]); // đổi chỗ
upheap(pa); // up cha nó
}
}
void push(int a) // đẩy giá trị a vào
{
nh++; // tăng số lượng
heap[nh] = a; // cho a vô
upheap(nh); // đẩy a lên
}
void downheap(int x)
{
int c = x*2; // con của x
if(c > nh)return; // không có con thì thoát
if(c < nh and heap[c+1] > heap[c]) c++;
// nếu nó còn con 2 thì chọn con lớn để khi kéo nó
// lên đảm bảo thằng này lúc làm cha sẽ lớn hơn
2
// thằng con không được làm cha
if(heap[x] < heap[c]){ // nếu kéo được thì kéo
swap(heap[x],heap[c]); // đổi chỗ
downheap(c); // down nó
}
}
void del(int x)
{
heap[x] = heap[nh]; // kéo thằng cuối lên x
nh; // giảm số phần tử
downheap(x); // cập nhật lại
upheap(x);
}
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.
III. BÀI TẬP ỨNG DỤNG CẤU TRÚC HEAP
1. KMIN http://vn.spoj.com/problems/KMIN
Ý tưởng: Ban đầu sort không giảm hai dãy a,b. Cho a[1] + b[i] với i = 1 -> n vào 1
heap_min. Duyệt k lần , mỗi lần lấy gốc ra rồi cho a[i+1] + b[j] vào với i, j là vị trí
của nút vừa lấy ra, nếu i = n thì thôi.
1. const fi=”;
2.
fo=”;
3. type mang=array[1..50000] of longint;
4.
sum=record i, j: longint; end;
5. var
f: text;
6.
a, b: mang;
7.
m, n, k, top: longint;
8.
heap: array[1..50000] of sum;
9. {——————————————————————}
10.
procedure enter;
11.
var
i: longint;
12.
begin
13.
assign(f, fi);
14.
reset(F);
15.
readln(f, m, n, k);
16.
for i:=1 to m do readln(f, a[i]);
17.
for i:=1 to n do readln(f, b[i]);
18.
close(F);
19.
end;
20.
{——————————————————————}
3
21.
22.
23.
24.
25.
function cmp(x, y: sum): boolean;
begin
exit(a[x.i]+b[x.j]>=a[y.i]+b[y.j]);
end;
{——————————————————————-
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
procedure swap(i, j: longint);
var
tg: sum;
begin
tg:=heap[i];
heap[i]:=heap[j];
heap[j]:=tg;
end;
{————————————————–}
procedure upheap(i: longint);
begin
if (i=1) or cmp(heap[i], heap[i div 2]) then exit;
swap(i, i div 2);
upheap(i div 2);
end;
{——————————————————————}
procedure downheap(i: longint);
var
j: longint;
begin
j:=i*2;
if j>top then exit;
if (j
CẤU TRÚC HEAP VÀ ỨNG DỤNGI. LỜI NÓI ĐẦUCó thể nói Heap là 1 cấu trúc hữu dụng vào bậc nhất trong giải toán. Trongkhoa học máy tính, đống (tiếng Anh: heap) là một cấu trúc dữ liệu dựa trên cây thỏamãn tính chất đống: nếu B là nút con của A thì khóa(A)≥khóa(B) (HEAP MAX) .Một hệ quả của tính chất này là khóa lớn nhất luôn nằm ở nút gốc. Do đó một đốngnhư vậy thường được gọi là đống-max. Nếu mọi phép so sánh bị đảo ngược khiếncho khóa nhỏ nhất luôn nằm ở nút gốc thì đống đó gọi là đống-min. Thông thườngmỗi nút có không quá hai nút con. Mục đích của heap trong các bài các bài toán tin làta có thể truy xuất phần tử lớn nhất hay nhỏ nhất có trong một mảng lưu trữ hiện tại.Do đó có 2 loại là heap_max và heap_min. Đống là một cách thực hiện kiểu dữ liệutrừu tượng mang tên hàng đợi ưu tiên. Đống có vai trò quan trọng trong nhiều thuậttoánMột số ứng dụng của Heap:+ Heapsort: Một trong những phương pháp sắp xếp tại chỗ tốt nhất+ Thuật toán lựa chọn: có thể sử dụng đống để tìm phần tử lớn nhất, nhỏ nhất, trungvị, phần tử lớn thứ k, trong thời gian tuyến tính.+ Thuật toán cho đồ thị: nhiều thuật toán cho đồ thị sử dụng cấu trúc dữ liệu đốngchẳng hạn như thuật toán Dijkstra, hay thuật toán Prim.Các thao tác thường gặp trên đống là:+ Tìm-max (tìm-min): tìm khóa lớn nhất trong đống-max (tìm khóa nhỏ nhất trongđống-min).+ Xóa-max (xóa-min): xóa nút gốc của đống-max (đống-min)+ tăng-khóa (giảm-khóa): thay đổi giá trị một khóa trong đống-max (đống-min)+ chèn: chèn thêm một khóa mới vào đống+ hợp: hợp hai đống lại thành một đống mới chứa tất cả các khóa của cả haiII. CẤU TRÚC HEAPHeap được biểu diễn bằng cây nhị phân, nút k trên cây sẽ có hai nút con là 2*kvà 2*k+1, có cha là k div 2. Heap[k] tùy theo loại heap mà nó lớn hơn con nó hay chanó. Mỗi khi ta thay đổi một phần tử bất kì trong heap thì ta sẽ cập nhật lại heap trongkhoảng thời gian log n. Có hai thao tác đối với heap là upheap và downheap.Heap sẽ cần biến nh để quản lí số lượng phần tử của heap.Ví dụ với HEAP MAXCá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 đó- Del: 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.Trong code x là vị trí, a là giá trị, nh là số phần tử, pa là cha của x, c là con củax.void upheap(int x)if (x == 1) return; // x là gốc thì làm gì có chaint pa = x/2; // cha của xif(heap[x] > heap[pa]){ // x hơn cha nó nên đi lênswap(heap[x],heap[pa]); // đổi chỗupheap(pa); // up cha nóvoid push(int a) // đẩy giá trị a vàonh++; // tăng số lượngheap[nh] = a; // cho a vôupheap(nh); // đẩy a lênvoid downheap(int x)int c = x*2; // con của xif(c > nh)return; // không có con thì thoátif(c < nh and heap[c+1] > heap[c]) c++;// nếu nó còn con 2 thì chọn con lớn để khi kéo nó// lên đảm bảo thằng này lúc làm cha sẽ lớn hơn// thằng con không được làm chaif(heap[x] < heap[c]){ // nếu kéo được thì kéoswap(heap[x],heap[c]); // đổi chỗdownheap(c); // down nóvoid del(int x)heap[x] = heap[nh]; // kéo thằng cuối lên xnh; // giảm số phần tửdownheap(x); // cập nhật lạiupheap(x);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ụngHeap.III. BÀI TẬP ỨNG DỤNG CẤU TRÚC HEAP1. KMIN http://vn.spoj.com/problems/KMINÝ tưởng: Ban đầu sort không giảm hai dãy a,b. Cho a[1] + b[i] với i = 1 -> n vào 1heap_min. Duyệt k lần , mỗi lần lấy gốc ra rồi cho a[i+1] + b[j] vào với i, j là vị trícủa nút vừa lấy ra, nếu i = n thì thôi.1. const fi=”;2.fo=”;3. type mang=array[1..50000] of longint;4.sum=record i, j: longint; end;5. varf: text;6.a, b: mang;7.m, n, k, top: longint;8.heap: array[1..50000] of sum;9. {——————————————————————}10.procedure enter;11.vari: longint;12.begin13.assign(f, fi);14.reset(F);15.readln(f, m, n, k);16.for i:=1 to m do readln(f, a[i]);17.for i:=1 to n do readln(f, b[i]);18.close(F);19.end;20.{——————————————————————}21.22.23.24.25.function cmp(x, y: sum): boolean;beginexit(a[x.i]+b[x.j]>=a[y.i]+b[y.j]);end;{——————————————————————-26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.procedure swap(i, j: longint);vartg: sum;begintg:=heap[i];heap[i]:=heap[j];heap[j]:=tg;end;{————————————————–}procedure upheap(i: longint);beginif (i=1) or cmp(heap[i], heap[i div 2]) then exit;swap(i, i div 2);upheap(i div 2);end;{——————————————————————}procedure downheap(i: longint);varj: longint;beginj:=i*2;if j>top then exit;if (j
