排序篇:heap

public static void heapSort() {
    int[] arr = {0, 5, 6, 333, 5, 8, 999, 7, 7, 5, 45, 3};
    int heapSize = arr.length - 1;//堆的大小，
    buildHeap(arr, heapSize);//建堆，递归调用maxHeapify
    System.out.println(Arrays.toString(arr));

    for (int i = arr.length - 1; i > 0; i--) {
        // 堆从index=1开始建立，方便操作
        swap(arr, 1, i);
        //每一次把第一个元素（最大）放到堆的最后一个节点，所以每一次堆的大小减一
        heapSize--;
        maxHeapify(arr, 1, heapSize);
    }
    System.out.println(Arrays.toString(arr));
}

private static void maxHeapify(int[] arr, int index, int heapSize) {

    int leftIndex = index << 1;
    int rightIndex = leftIndex + 1;
    int largestIndex = index;
    if (leftIndex <= heapSize && arr[leftIndex] > arr[index]) {
        largestIndex = leftIndex;
    }
    if (rightIndex <= heapSize && arr[rightIndex] > arr[largestIndex]) {
        largestIndex = rightIndex;
    }
    if (largestIndex != index) {
        swap(arr, index, largestIndex);
        maxHeapify(arr, largestIndex, heapSize);
    }

}

private static void buildHeap(int[] arr, int heapSize) {
    //(arr.length/2)从非叶子节点处开始遍历
    for (int i = arr.length / 2; i > 0; i--) {
        maxHeapify(arr, i, heapSize);
    }
}

public static void swap(int arr[], int j, int i) {
    int tmp = arr[j];
    arr[j] = arr[i];
    arr[i] = tmp;
}