Phân tích thuật toán Heap Sort


Fri Apr 27 2018


phân tích thuật toán heap sort

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.

 

parent and children

 

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:

heap as array

 

 

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 2j2j+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;

 

Với array cũ, ta sẽ thêm phần tử P vào.

 

them p vao heap array

 

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

build heap

Remove:

remove heap sort

 

Độ 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.



avatar
Curious developer
Tech seeker