编辑代码

public class HeapSort {  
    public void sort(int arr[]) {  
        int n = arr.length;  
  
        // 构建大顶堆  
        for (int i = n / 2 - 1; i >= 0; i--)  
            heapify(arr, n, i);  
  
        // 一个个交换元素  
        for (int i = n - 1; i >= 0; i--) {  
            // 当前最大的元素 arr[0] 和 arr[i] 交换  
            int temp = arr[0];  
            arr[0] = arr[i];  
            arr[i] = temp;  
  
            // 重新对剩下的元素进行 heapify  
            heapify(arr, i, 0);  
        }  
    }  
  
    void heapify(int arr[], int n, int i) {  
        int largest = i; // Initialize largest as root  
        int left = 2 * i + 1; // left = 2*i + 1  
        int right = 2 * i + 2; // right = 2*i + 2  
  
        // 如果左子节点大于根节点  
        if (left < n && arr[left] > arr[largest])  
            largest = left;  
  
        // 如果右子节点大于目前的最大值  
        if (right < n && arr[right] > arr[largest])  
            largest = right;  
  
        // 如果最大值不是根节点，那么将最大值交换到根节点，并继续heapify  
        if (largest != i) {  
            int swap = arr[i];  
            arr[i] = arr[largest];  
            arr[largest] = swap;  
  
            // 递归地对受影响的子堆进行heapify  
            heapify(arr, n, largest);  
        }  
    } 

    public static void print(int arr[]){
        System.out.println("Sorted array is");  
        for (int i = 0; i < arr.length; ++i)  
            System.out.print(arr[i] + " ");
        System.out.println("\n\n");
    }

    public static void main(String[] args) {
        int emptyArr[] = {};  
        int arr[] = {12, 11, 13, 5, 6, 7};   
        int arr1[] = {12, 11, 13, 11, 2, -1};
        int arr2[] = {1, 2, 3};
        HeapSort hs = new HeapSort();  
        hs.sort(emptyArr);
        hs.sort(arr);
        hs.sort(arr1);
        hs.sort(arr2); 
  
        print(emptyArr); 
        print(arr); 
        print(arr1); 
        print(arr2); 
    }

}