package secondChapter;

import java.util.Random;

public class HeapSort {
    
    private static int AHeapSize;
    
    public static void main(String[] args) {
        
        HeapSort hs = new HeapSort();
        int[] A = new int[10];
        //产生随机数组
        for(int i=0;i<A.length;i++){
            A[i] = hs.generateRandomInt(50);
        }
        System.out.print("Original array：");
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i]+" ");
        }
        System.out.println();
        
        hs.heap_sort(A);
        
        System.out.print("Sorted array: ");
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i]+" ");
        }
    }
    
    //HEAPSORT过程
    public void heap_sort(int[] A) {
        AHeapSize = A.length;
        build_max_heap(A);
        
        System.out.print("build_max_heap: ");
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i]+" ");
        }
        System.out.println();
        
        
        for(int i=A.length;i>1;i--){
            int temp = A[0];
            A[0] = A[i-1];
            A[i-1] = temp;
            
            AHeapSize -= 1;
            max_heapify(A,1);
        }
    }
    
    //HUILD-MAX-HEAP过程
    public void build_max_heap(int[] A) {
        for(int i=A.length/2;i>0;i--){
            max_heapify(A,i);
        }
    }
    
    //MAX-HEAPIFY过程
    public void max_heapify(int[] A, int i) {    //i为 元素下标+1
        int l = 2*i;
        int r = 2*i+1;
        
        int largest;
        if(l<=AHeapSize && A[l-1]>A[i-1]){
            largest = l;
        }else{
            largest = i;
        }
        if(r<=AHeapSize && A[r-1]>A[largest-1]){
            largest = r;
        }
        if(largest!=i){
            int temp = A[i-1];
            A[i-1] = A[largest-1];
            A[largest-1] = temp;
            
            max_heapify(A, largest);
        }
    }
    
    private Random rd = new Random();
    public int generateRandomInt(int bound) {
        return rd.nextInt(bound);
    }
    
}