package com.jiucaiyuan.net.algrithm.sort;



import java.util.PriorityQueue;



/**

 * <pre>

 * 堆排序扩展

 *   一个几乎有序的数组，

 *   几乎有序是指，如果把数组排好顺序的话，

 *   每个元素移动的距离可以不超过k，这个k相对于数组来说比较小，

 *   请选择合适的排序算法针对这个数组进行排序

 *

 * 	 时间复杂度O(N*logk)  空间复杂度O(k)

 *

 * </pre>

 * Created by jiucaiyuan on 2022/3/31.

 */

public class HeapSortExtension {

    /**

     * 堆排序算法

     *

     * @param arr

     * @return

     */

    public static void sortedArrDistanceLessK(int[] arr, int k) {

        //默认是小根堆

        PriorityQueue<Integer> heap = new PriorityQueue<>();

        //把k个数放入小根堆

        int index = 0;

        for (; index <= Math.min(arr.length, k); index++) {

            heap.add(arr[index]);

        }

        //把数组剩下的数逐个放入小根堆，并逐个弹出小根堆头结点

        int i = 0;

        for (; index < arr.length; i++, index++) {

            heap.add(arr[index]);

            arr[i] = heap.poll();

        }

        //如果堆不为空，全部弹出

        while (!heap.isEmpty()) {

            arr[i++] = heap.poll();

        }

    }



    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};

        print(arr);

        sortedArrDistanceLessK(arr, 3);

        print(arr);

    }



    private static void print(int[] arr) {

        if (arr == null) {

            return;

        }

        for (int a : arr) {

            System.out.print(a + "\t");

        }

        System.out.println();

    }

}