Sắp xếp vun đống Heap sort

Sắp xếp vun đống Heap sort Sắp xếp vun đống - Heap sort Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này. Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong qua trình sắp xếp. Giả sử dữ liệu cần sắp xếp được bố trí theo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau : heap Các phần tử tốt nhất (xấu nhất) sẽ được dời lên trên Cấu trúc heap Heap là một cấu trúc dữ liệu dạng hình cây có tính chất sau: Mổi một phần tử sẽ có nhiều nhất 2 phần tử là con của nó (phần tử liên đới) Bất kỳ Phần tử ở trên (cha) sẽ có giá trị lớn hơn giá trị 2 phần tử con của nó Phần tử đầu (phần tử gốc) sẽ là phần tử có giá trị lớn nhất trong heap Cấu trúc heap 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 12 > 11, 12 > 4 16 là giá trị lớn nhất trong heap Heap có các tính chất sau : Tính chất 1 : Nếu al , al+1 ,al+2... , ar là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, dãy con còn lại vẫn là một heap. Tính chất 2 : Nếu a1 , a2 ,... , an là một heap thì phần tử a1 (đầu heap) luôn là phần tử lớn nhất trong heap. Tính chất 3 : Mọi dãy al , al+1 ,al+2... , ar với 2l > r  là một heap. Cấu trúc heap Cài đặt cấu trúc heap bằng mảng a0, a1 ,... , ar thoả các quan hệ sau với mọi i ﻴ [0, r]: - ai   a2i+1 - ai  >= a2i+2 (a2i+1, a2i+2) là các cặp phần tử liên đới phần tử a0 (đầu heap) luôn là phần tử lớn nhất trong heap. Vậy ak có phần tử liên đới là a2k+1, a2k+2 Phần tử cha của nó la a(k-1)/2 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 a0= 16  gốc a1=12 có 2 phần tử liên đới là a 2x1+1=a3 =11 a2x1+2=a4=4 a12=8 có phần tử cha nó là a(12-1)/2 =a5 =9 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 Cấu trúc heap Vấn đề cần quan tâm Làm sao xây dựng heap Thêm 1 phần tử Xóa 1 phần tử  phải đảm bảo tính chất heap Cấu trúc heap Thêm 1 phần tử Thêm vào cuối mảng  mất tính chất heap Cập nhật lại heap (upheap) Bước 1:tại k kiểm tra so với cha của nó (k1-1)/2 Nếu ak a(k-1)/2 đổi vị trí  bước 1 Cấu trúc heap Thêm 15 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 Cấu trúc heap 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 15 15 16 15 Cấu trúc heap 16 12 14 11 4 6 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 15 7 15 Cấu trúc heap 16 12 14 11 4 6 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 15 7 15 Cấu trúc heap 16 12 14 11 4 6 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 15 7 Cấu trúc heap (C) Thuật toán upheap Void uphead(int a[], int N){ Int k=N-1; While (k>0)&&(a[k]>a[(k)/2]) {hoanvi(a[k],a[k/2]);k=k/2;} } Cấu trúc heap (C#) Thuật toán upheap Void uphead(){ Int k=N-1; While (k>0)&&(a[k]>a[(k-1)/2]) { hoanvi(ref a[k],ref a[(k-1)/2]); k=(k-1)/2; } } Cấu trúc heap Xóa phần tử Thông thường cấu trúc heap thường lấy phần tử gốc (đầu) ra khỏi heap  mất tính chất heap cập nhật heap Cấu trúc heap Cách giải quyết 1: Chọn trong 2 phần tử liên đới phần tử nào lớn hơn thì đưa lên  mảng bị phân mảnh, trống Cấu trúc heap Lấy gốc ra 16 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 Cấu trúc heap 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 Cấu trúc heap 9 11 4 6 7 1 2 12 8 0 10 3 5 13 9 11 4 14 12 7 6 2 1 0 8 3 10 5 13 14 Cấu trúc heap Lấy gốc ra 16 10 11 4 6 7 1 2 12 8 0 9 13 5 10 3 11 4 14 12 7 6 2 1 0 8 9 13 5 3 14 Cấu trúc heap Lấy gốc ra 16 11 4 6 7 1 2 12 8 0 9 13 5 11 4 14 12 7 6 2 1 0 8 9 13 5 14 10 3 3 10 bị trống Cấu trúc heap Cách giải quyết 2: Đưa phần tử cuối lên thay thế Bước 1 :Chọn phần tử lớn nhất trong phần tử đang xét và 2 phần tử liên đới đưa lên Nếu là ak dừng Nếu là a2k+1, thay ak với a2k+1 K=2k+1 bước 1 Nếu là a2k+2, thay ak với a2k+2 K=2k+2 bước 1  cập nhật downheap Cấu trúc heap 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 5 5 Cấu trúc heap 5 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 12 14 11 4 9 13 7 6 2 1 0 8 3 10 Cấu trúc heap Lấy gốc ra 16 9 11 4 6 7 1 2 12 8 0 10 3 13 9 11 4 14 12 7 6 2 1 0 8 3 10 5 13 14 5 Cấu trúc heap 10 11 4 6 7 1 2 12 8 0 9 13 10 3 11 4 14 12 7 6 2 1 0 8 9 13 5 3 14 5 Cấu trúc heap 11 4 6 7 1 2 12 8 0 9 13 5 11 4 14 12 7 6 2 1 0 8 9 13 5 14 10 3 3 10 downheap void downheap(int l, int r) { int x, i, j; int vtconmax; int Flag = 1; i = l; j = 2 * i + 1; // (aj , aj+1) la cac phan tu lien doi cua i x = tappt[i]; while ((j 0 (heap còn phần tử ): Lặp lại Bước 2       Ngược lại : Dừng heapsort Dựa trên tính chất 3, ta có thể thực hiện giai đoạn 1 bắng cách bắt đầu từ heap mặc nhiên an/2+1 , an/2+2 ... an, lần lượt thêm vào các phần tử an/2, an/2-1, ., a1 ta sẽ nhân được heap theo mong muốn. Như vậy, giai đoạn 1 tương đương với n/2 lần thực hiện bước 2 của giai đoạn 2. Ví dụ : sắp xếp mảng : Cấu trúc heap 2 12 9 5 4 6 7 1 16 14 3 8 0 10 13 11 2 12 9 5 4 14 3 7 6 16 1 0 8 13 10 11 Phẩn tử liên đới i= N/2=8 Cấu trúc heap 2 12 9 5 4 6 11 1 16 14 3 8 0 10 13 7 2 12 9 5 4 14 3 11 6 16 1 0 8 13 10 7 Phẩn tử liên đới i= 7 Cấu trúc heap 2 12 9 5 4 6 11 1 16 14 13 8 0 10 3 7 2 12 9 5 4 14 13 11 6 16 1 0 8 3 10 7 Phẩn tử liên đới i= 6 Cấu trúc heap 2 12 9 5 4 6 11 1 16 14 13 8 0 10 3 7 2 12 9 5 4 14 13 11 6 16 1 0 8 3 10 7 Phẩn tử liên đới i= 5 Cấu trúc heap 2 12 9 5 16 6 11 1 4 14 13 8 0 10 3 7 2 12 9 5 16 14 13 11 6 4 1 0 8 3 10 7 Phẩn tử liên đới i= 4 Cấu trúc heap 2 12 9 11 16 6 5 1 4 14 13 8 0 10 3 7 2 12 9 11 16 14 13 5 6 4 1 0 8 3 10 7 Phẩn tử liên đới i= 4 Cấu trúc heap 2 12 9 11 16 6 7 1 4 14 13 8 0 10 3 5 2 12 9 11 16 14 13 7 6 4 1 0 8 3 10 5 Phẩn tử liên đới i= 3 Cấu trúc heap 2 12 14 11 16 6 7 1 4 9 13 8 0 10 3 5 2 12 14 11 16 9 13 7 6 4 1 0 8 3 10 5 Phẩn tử liên đới i= 3 Cấu trúc heap 2 12 14 11 16 6 7 1 4 9 13 8 0 10 3 5 2 12 14 11 16 9 13 7 6 4 1 0 8 3 10 5 Phẩn tử liên đới i= 2 Cấu trúc heap 2 16 14 11 12 6 7 1 4 9 13 8 0 10 3 5 2 16 14 11 12 9 13 7 6 4 1 0 8 3 10 5 Phẩn tử liên đới i= 2 Cấu trúc heap 2 16 14 11 12 6 7 1 4 9 13 8 0 10 3 5 2 16 14 11 12 9 13 7 6 4 1 0 8 3 10 5 Phẩn tử liên đới i= 1 Cấu trúc heap 16 2 14 11 12 6 7 1 4 9 13 8 0 10 3 5 16 2 14 11 12 9 13 7 6 4 1 0 8 3 10 5 Phẩn tử liên đới i= 1 Cấu trúc heap 16 12 14 11 2 6 7 1 4 9 13 8 0 10 3 5 16 12 14 11 2 9 13 7 6 4 1 0 8 3 10 5 Phẩn tử liên đới i= 1 Cấu trúc heap 16 12 14 11 4 6 7 1 2 9 13 8 0 10 3 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 Heapsort- hiểu chỉnh heap Thủ tục hiệu chỉnh dãy al , al+1 ...ar thành heap void Shift (int a[ ], int l, int r ) Hiệu chỉnh dãy a0 , a1 ...aN-1 thành heap: void CreateHeap(int a[], int N-1 ) Giả sử có dãy al , al+1 ...ar, trong đó đoạn al+1 ...ar, đã là một heap. Ta cần xây dựng hàm hiệu chỉnh al , al+1 ...ar thành heap. Ðể làm điều này, ta lần lượt xét quan hệ của một phần tử ai nào đó với các phần tử liên đới của nó trong dãy là a2i+1 và a2i+2, nếu vi phạm điều kiện quan hệ của heap, thì đổi chỗ ai với phần tử liên đới thích hợp của nó. Lưu ý việc đổi chỗ này có thể gây phản ứng dây chuyền: C void Shift (int a[ ], int l, int r ){ int x,i,j; i = l; j =2*i+1; // (ai , aj ), (ai , aj+1) là các phần tử liên đới x = a[i];  while ((j 0) do { Shift(a,l,N); l = l -1; }} Cách viết khác vơi C# public void createheap() { for (int i = (N - 1) / 2; i >= 0; i--) { downheap(i, N - 1); } } heapsort 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 5 12 14 11 4 9 13 7 6 2 1 0 8 3 10 16 14 12 13 11 4 9 10 7 6 2 1 0 8 3 5 heapsort 16 14 12 13 11 4 9 10 7 6 2 1 0 8 3 5 16 5 12 13 11 4 9 10 7 6 2 1 0 8 3 14 13 12 10 11 4 9 5 7 6 2 1 0 8 3 heapsort 16 16 14 13 12 10 11 4 9 5 7 6 2 1 0 8 3 14 3 12 10 11 4 9 5 7 6 2 1 0 8 13 12 11 10 7 4 9 5 3 6 2 1 0 8 heapsort 16 16 14 14 12 13 12 11 10 7 4 9 5 3 6 2 1 0 8 13 8 11 10 7 4 9 5 3 6 2 1 0 11 8 10 7 4 9 5 3 6 2 1 0 heapsort 16 16 14 14 12 13 13 11 8 10 7 4 9 5 3 6 2 1 0 12 0 8 10 7 4 9 5 3 6 2 1 11 10 8 9 7 4 0 5 3 6 2 1 heapsort 16 16 14 14 12 13 13 12 11 10 8 9 7 4 0 5 3 6 2 1 11 1 8 9 7 4 0 5 3 6 2 10 9 8 5 7 4 0 1 3 6 2 heapsort 16 16 14 14 12 13 13 12 11 11 10 8 7 5 6 4 0 1 3 2 9 8 5 7 4 0 1 3 6 2 10 9 2 8 5 7 4 0 1 3 6 heapsort 16 16 14 14 12 13 13 12 11 11 10 7 6 5 3 4 0 1 2 10 9 9 8 7 5 6 4 0 1 3 2 8 2 7 5 6 4 0 1 3 Heapsort (c) Khi đó hàm Heapsort có dạng sau : void HeapSort (int a[], int N){ int r; CreateHeap(a,N) r = N-1; // r là vị trí đúng cho phần tử nhỏ nhất while(r >= 0) do { Hoanvi(a[0],a[r]); r = r -1; Shift(a,0,r); }} Heapsort (c#) Khi đó hàm Heapsort có dạng sau : void HeapSort (){ int r; CreateHeap(0,spt-1) r = spt-1; // r là vị trí đúng cho phần tử nhỏ nhất while(r >= 0) do { Hoanvi(a[0],a[r]); r = r -1; Shift(a,0,r); }} Ðánh giá giải thuật Việc đánh giá giải thuật Heapsort rất phức tạp, nhưng đã chứng minh được trong trường hợp xấu nhất độ phức tạp O(Nlog2N)