Bài 9 (Java):Sắp xếp kiểu vun đống(Heap sort)

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ử.​

Tạo đống: xét i=n/2 xuống i=0

i là địa chỉ của cây đáng xet, largest là chỉ số của phần tử lớn nhất

left =2*i, right= 2*i+1 ( địa chỉ của cây con trái và cây con phải)

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)

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.

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:

 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 song đố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

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:

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);
           heap(a, largest);
        }
    }

    public static void exchange(int i, int j){
        int t=a[i];
        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);
        }
    }

    public static void main(String[] args) {
        int []a1={1,3,7,2,4,6,9,8,5};
        sort(a1);
        for(int i=0;i<a1.length;i++){
            System.out.print(a1[i] + " ");
        }
    }
}

​
Học lập trình Java tại TT iplus-academy 
hoc lap trinh java tại TT iplus-academy 
hoc lap trinh Android tại TT itplus.academy