Trước khi đến với heap, hay heap sort, chúng ta cần phải hiểu về priority queue (hàng đợi ưu tiên) và bản chất “transform and conquer” (2 bước, bước đầu transform/ thay đổi bài toán theo kiểu dễ xử lý và bước sau sẽ giải nó).
Cấu trúc dữ liệu: Priority-Queue
Hỗ trợ 2 kiểu sau:
tạo một phần tử (item) mới
xóa phần tử có giá trị lớn nhất (có priority lớn nhất)
Sự khác nhau giữa priority queue và queue
Khi chúng ta xóa một item khỏi kiểu dữ liệu này, đó là item có priority lớn nhất.
Implementation priority queue
Có 2 cách để hiện thực hóa
1. Sử dụng array
Khi tạo (insert), chúng ta đơn giản chỉ cần tăng N – số phần tử trong array, và gán giá trị mới vào A[N]. Như khi xóa phần tử đó, chúng ta cần loop qua tất cả phần tử để tìm vị trí (key hay còn gọi là index) của phần tử có giá trị lớn nhất. (Cần O(n))
2. Sử dụng Heap
Cấu trúc dữ liệu Heap
Khi insert, chúng đảm bảo parents phải lớn hơn child.
Vị trí (key/ index) của cây heap phải thỏa mãn các điều kiện sau: (1)
Giá trị trong mỗi key phải lớn hơn hoặc bằng giá trị key trong children của nó. Từ đó ta hiểu key có giá trị lớn nhất chính là root (gốc của cây, phần tử nằm ở vị trí cao nhất).
Biểu diễn Heap dưới dạng array
Chúng ta có thể biểu diễn heap dưới dạng array qua ví dụ sau:
k | a[k] |
0 | X |
1 | T |
2 | O |
3 | G |
4 | S |
5 | M |
6 | N |
7 | A |
8 | E |
9 | R |
10 | A |
11 | I |
Từ hình vẽ, ta có thể suy luận ra được:
parent của node có vị trí j nằm ở vị trí j / 2 (j div 2)
Hai children của node có vị trí j là nằm ở các vị trí lần lượt 2jvà 2j+1
Chú ý rằng: trong 1 heap với N node, mỗi con đường từ root đến leaf (node nằm ở dưới cùng) có khoảng lgN node. (2)
Thuật toán Heap
Có hai thuật toán quan trọng liên quan đến Heap, đó là thêm (insert) phần tử mới và xóa (remove) phần tử lớn nhất ra khỏi heap.
1. Insert
Mỗi khi chúng ta thêm phần tử vào, ta bắt buộc phải tăng N, số phần tử trong array. Phần tử mới sẽ nằm ở vị trí a[N] với a là array cho sẵn. Nhưng việc thêm này không tuân theo các điều kiện được nhắc đến tại (1).
Do vậy, các phần tử trong array buộc phải đổi chỗ với nhau, và đổi chỗ không chỉ một lần.
Insert Operation
procedure upheap(k:integer)
var v: integer;
begin
v :=a[k]; a[0]:= maxint;
while a[k div 2] <= v do
begin a[k]:= a[k div 2 ]; k:=k div 2 end;
a[k]:= v
end;
procedure insert(v:integer);
begin
N:= N+1; a[N] := v ; upheap(N)
end;Remove Operation
Trong bước này, chúng ta sẽ giảm N, kích thước của heap.
Xóa phần tử lớn nhất của heap – a[0] và phần tử a[N] sẽ được đổi chỗ lên vị trí a[0] – vị trí root.
Nếu giá trị của root nhỏ hơn children của nó, nó sẽ được đổi chỗ lần nữa, hoặc nhiều lần nữa cho đến khi tìm được vị trí phù hợp. Quá trình này gọi là downheap
procedure downheap(k: integer);
label 0 ;
var j, v : integer;
begin
v:= a[k];
while k<= N div 2 do
begin
j:= 2*k;
if j < N then if a[j] < a[j+1] then
j:=j+1;
if v >= a[j] then go to 0;
a[k]:= a[j]; k:= j;
end;
0: a[k]: =v
end;
function remove: integer;
begin
remove := a[1];
a[1] := a[N]; N := N-1;
downheap(1);
end;Độ phức tạp của các operation trên heap
Tất cả các operation cơ bản với heap (insert, remove, downheap, upheap cần < 2lgN lần so sánh trên 1 heap với N phần tử.
Vì sao lại 2*lgN? Đó là bởi vì chúng ta cần downheap cho tất cả operation đó. Theo (2), vì mỗi path từ root đến leaf chỉ có lgN node, nên số lần so sánh tối đa cho mỗi operation là lgN.
Heap sort
Ý tưởng: như những kiến thức trên, heap sort cũng bao gồm 2 phần: build heap và remove theo thứ tự.
Mã giả – pseudo code (3)
N:=0;
for k:= 1 to M do
insert(a[k]); /* construct the heap */for k:= M downto 1 do
a[k]:= remove; /*putting the element removed into the
array a */(ví dụ) Build và remove với các số sau:
44 30 50 22 60
Build heap (top-down method):
Remove:
Độ phức tạp của Heap sort
Heap sort dùng < 3MlgM lần so sánh để sort một array có M phần tử.
Theo code ở (3):
Ta cần MlgM lần so sánh cho loop đầu tiên.
Ta cần 2MlgM lần so sánh cho loop thứ 2.
Tổng cộng: 3MlgM
Vậy là chúng ta đã tìm hiểu xong về Heap, hẹn gặp các bạn ở những bài sau.
