随笔记录

算法-堆排序

2022-3-31 diaba 算法

package com.jiucaiyuan.net.algrithm.sort;

/**
 * <pre>
 * 堆排序
 *   数组表示二叉树[0,1,2,3,4,5,6]       下标i的左子节点是2*i+1 ，右子节点是 2*i+2  ， 父节点是 (i-1)/2
 * 	 大根堆：以i为头的整棵树，最大值是i
 * 	 小根对：以i为头的整棵树，最小值是i
 *   优先级队列结构就是堆结构
 * 	 时间复杂度O(N*logN)  空间复杂度O(1)
 * </pre>
 * Created by jiucaiyuan on 2022/3/31.
 */
public class Sort06_HeapSort {
    /**
     * 堆排序算法
     *
     * @param arr
     * @return
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) { //O(N)
            heapInsert(arr, i);  //O(logN)
        }

        //这个过程处理完，arr也成为大根堆
//        for (int i = arr.length; i > 0; i--) {
//            heapify(arr, i, arr.length);
//        }

        int heapSize = arr.length;
        while (heapSize > 0) {  //O(N)
            swap(arr, 0, --heapSize);     //O(logN)
            heapify(arr, 0, heapSize);  //O(1)
        }
    }

    /**
     * 指定index位置的数加入到arr[0~index-1]所表示的大根堆中
     *
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        //如果index位置的数比父节点数大
        while (arr[index] > arr[(index - 1) / 2]) {
            //当前数和父节点数交换
            swap(arr, index, (index - 1) / 2);
            //再判断和父节点大小
            index = (index - 1) / 2;
        }
    }

    /**
     * 指定index位置的数加入到arr[0~index-1]所表示的大根堆中
     *
     * @param arr
     * @param index
     */
    public static void heapify(int[] arr, int index, int heapSize) {
        int leftChild = 2 * index + 1;
        //如果节点有子节点
        while (leftChild < heapSize) {
            //选择较大的子节点下标
            int bigger = leftChild + 1 < heapSize && arr[leftChild] < arr[leftChild + 1]
                    ? leftChild + 1 : leftChild;
            //父和较大子节点较大的数的下标给bigger
            bigger = arr[index] > arr[bigger] ? index : bigger;
            //如果父就是较大的数，即不用再处理了
            if (index == bigger) {
                return;
            }
            //较大的数和当前数交换
            swap(arr, index, bigger);

            //下次继续判断当前数
            index = bigger;
            leftChild = 2 * index + 1;
        }
    }

    /**
     * @param arr
     * @param l
     * @param r
     */
    private static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {12, 5, 3, 7, 3, 8, 4, 3, 2, 2, 6, 8, 6, 0, 9, 5, 3};
        heapSort(arr);
        print(arr);
    }

    private static void print(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int a : arr) {
            System.out.print(a + "\t");
        }
        System.out.println();
    }
}