Sắp xếp kiểu vun đống(Heap sort) trong java

Tiếp tục các bài hướng dẫn về sắp xếp trong hoc lap trinh java

1. Định nghĩa đống:

- Đống là một cây nhị phân hoàn chỉnh mà mỗi nút được gắn một khóa sao cho khóa ở nút cha bao giờ cũng lớn hơn khóa ở nút con.
- Được lưu trữ trong máy bởi 1 vecto K
​

• Đỉnh đống là nút được đánh số 1 có giá trị lớn nhất
• Chọn khóa lớn nhất trong dãy khóa sẽ cho thuận lợi hơn nếu tạo một đống ứng với dãy khóa này
• Cây nhị phân hoàn chỉnh ta thấy ở trên được biểu diễn bằng 1 vec tơ, vậy ngược lại 1 vecto sẽ được biểu diễn bằng mộ cây nhị phân hoàn chỉnh.

2.Tạo đống:

- Xét cây nhị phân hoàn chỉnh có n nút mỗi nút là một khóa có giá trị xác định. và muốn tạo cây đó thành đống:​

• Các cây con của cây này cũng phải là đống
• Một nút lá cũng được goi là đống
• Cây nhị phân hoàn chỉnh có n nút thì chỉ có n/2 nút đc gọi là cha

- vậy ta sẽ tạo đống cho cây nhị phân từ dưới lên. Ta sẽ bắt đầu với các lá, ta sẽ tạo đôgns cho một cây mà 2 cây con của nó là là rồi cứ tiếp tục như vậy :
tạo đôgns cho một cây con hoàn chình có gốc đánh số thứ tự i và 2 cây con của nó đã là lá rồi:

Ở đây làm việc với vecto A gồm n phần tử.​

1. Tạo đống: xét i=n/2 xuống i=0
2. i là địa chỉ của cây đáng xet, largest là chỉ số của phần tử lớn nhất
3. left =2*i, right= 2*i+1 ( địa chỉ của cây con trái và cây con phải)
4. if(left <= n and a
   > a)
   largest=left; (so sánh cây con trái và gốc)
   
   [*]else largest = i;
   [*] if(right <= n and a> a[largest])
   largest=right; (so sánh cây con phải với thằng lớn nhất)
5. nếu chỉ số của thằng lớn nhất không phải là i thì ta sẽ đổi chỗ chung cho nhau tức là a đổi chỗ với a[largest] vậy ta đc phần tử lớn nhất trên đỉnh => được 1 đống.
6. sau khi đổi chỗ ta sẽ kiểm tra phần tử largest =i hay không nếu không bằng phải lặp lại thủ tục lần nữa.

code java:

PHP:

 public static void buildheap(int []a)[/I][/I][/I][/LEFT]
[I][I][I]
   n=a.length-1;
[LEFT]        for(int i=n/2;i>=0;i--){
            heap(a,i);
        }
    }

    public static void heap(int[] a, int i){
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
  
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            int t=a[i];a[i]=a[j];a[j]=t;
            heap(a, largest);
        }
    }

​

​

Vậy là ta xong bược 1 tạo ra được 1 đống

3. Sắp xếp kiểu vun đống.

Sau khi tao xong đống ta sẽ sắp xếp lại để được dãy tăng dần theo ý mình: 

exchange(int i, int j){
int t=a;
a=a[j];
a[j]=t; 
}

sort(int []a0){
a=a0;
buildheap(a);

for(int i=n;i>0;i--){
exchange(0, i);
n=n-1;(sau khi đổ chỗ a[n] sẽ là phần tử lớn nhất và đugns vị trí nên ta n-- để không xét tới a[nư nữa)
heap(a, 0);(bước này sau khi đổi chỗ lại thực hiện xắp xếp lại cho đúng thành đống)

code java

PHP:

public static void exchange(int i, int j){[/I][/I][/I][/I][/I][/LEFT]
[I][I][I][I][I]
    int t=a[i];
[LEFT]        a[i]=a[j];
        a[j]=t;
        }

    public static void sort(int []a0){
        a=a0;
        buildheap(a);
  
        for(int i=n;i>0;i--){
            exchange(0, i);
            n=n-1;
            heap(a, 0);

​và đây là một code đầy đủ để sắp xếp 1 mảng bất kì theo phương pháp vun đống:

PHP:

public class HeapSort[/I][/I][/I][/I][/I][/LEFT]
[I][I][I][I][I]
{
[LEFT]    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;


    public static void buildheap(int []a){
        n=a.length-1;
        for(int i=n/2;i>=0;i--){
            maxheap(a,i);
        }
    }

    public static void heap(int[] a, int i){
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
  
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            exchange(i,largest);