[DataStructure]HeapSort(堆積排序)

HeapSort是利用堆積樹(Heap Tree)的性質來排序，堆積樹為完全二元樹(Complete Binary Tree)的一種，父節點大於兩個子節點稱為最大堆積樹，反之則稱為最小堆積樹

HeapSort原理就是將堆積樹根(最大or小值)與最後一個節點調換，將最後一個節點(原樹根)取出，並加入已排序數列，再將樹調整為堆積樹

最小堆積樹程式步驟：
1.由根或葉走訪二元樹
2.如遇子節點比父節點小時，子節點與父節點交換
3.遞迴繼續往樹根比
4.回到原本二元樹的走訪

HeapSort程式步驟：
1.將二元樹排列成堆積樹
2.根與葉交換，取出葉(原先的根)
3.重新排列堆積樹
4.重複

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Iterator;
public class heapSort {
    private static int [] arr = {0,10,25,15,30,26,20,29,35,40,27,28,22,12};
    private static ArrayList<Integer> result = new ArrayList<Integer>();
    public static void main(String [] argv) {
        HeapSort();
    }

    public static void HeapTree() {
        int len = arr.length - 1;
        int n = 1;
        while (n * 2 <= len) {
            int left = n * 2;
            int right = n * 2 + 1;

            if (arr[left] < arr[n]) {
                swap(left,n);
                BubbleSort(n);
            }

            if (right > len) {
                break;
            }

            if (arr[right] < arr[n]) {
                swap(right,n);
                BubbleSort(n);
            }
            n++;
        }
    }

    public static void BubbleSort(int n) {
        while (n / 2 > 0) {
            if (arr[n] < arr[n / 2]) {
                swap(n,n / 2);
            }
            n /= 2;
        }
    }

    public static void HeapSort() {
        HeapTree();
        int len = arr.length - 1;
        while (len > 0) {
            swap(1,len);
            result.add(arr[len]);
            arr = Arrays.copyOf(arr, len--);
            HeapTree();
        }
        show();
    }

    public static void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void show() {
        Iterator it = result.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
    }
}