Min Heap Sorting

Question: Given an unsorted array, the array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array. We can sort such arrays more efficiently with the help of Heap data structure. Implement the following algorithm that uses a Heap:
- Create a Min Heap of size k+1 with first k+1 elements.
- One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.

Solution

static void MinHeapSorting(int[] numberList, int length, int k) { 
    //Creating minHeap 
    PriorityQueue<Integer> queue = new PriorityQueue<>(); 
    //Add first k + 1 items to min heap 
    for (int i = 0; i < k + 1; i++) { 
        queue.add(numberList[i]); 
    } 
    int index = 0; 
    for (int i = k + 1; i < length; i++) { 
        numberList[index++] = queue.peek(); 
        queue.poll(); 
        queue.add(numberList[i]); 
    } 
    Iterator<Integer> itr = queue.iterator(); 
    while (itr.hasNext()) { 
        numberList[index++] = queue.peek(); 
        queue.poll(); 
    } 
}