In JAVA code write a function heapSort that uses locality aware sorting. Use d as the number of elements/places a integer can move back or fourth.

Head of heapSort function:

.

.

public static void heapSort(int[] arr, int d) {

}

.

.

Image is also attached for better understanding:

Locality-Aware Heapsort. In regular Heapsort, we turn the array into a heap and then use the sortdown method to pull out the maximum value and put it in its final position (at the end of the currently unsorted array. That increases the sorted part and decreases the size of the heap. To take locality awareness into account, you need to decide on a few options. Doing regular Heapsort in place is pretty straightforward. However, doing locality-aware Heapsort in place is more challenging. Because of that, you have the option to do it in place or to use an extra data structure (a heap). Guidelines for Heapsort using an extra data structure (not in place): The size of your heap should not be bigger than d+1. The first thing you should determine is what kind of heap you need--min or max? Think of your heap as a kind of sliding window for the elements. What do you do when the window is full? You'll remove an element and put it into the array--but which one and where does that element go? Then what do you do with the next element? The runtime of this implementation should not be worse than O(Nlogd)