Skip to content
Advertisement

Heapsort Within a Given Range

I am trying to write a Heapsort method that only performs the sort within a given range passed into the method. The ranges low and high are passed in and these values correspond to values inside the heap, not indices of the heap. For example, the input array might be: 28 10 49 20 59 61 17 and if low = 49 and high = 61, the resulting array after the Heapsort would look like this: 28 10 20 49 59 61 17. The values outside of the range remain unchanged. I already have a working Heapsort method but my question is how can modify this method to sort within a passed range?

public static void heapSort(int[] array, int low, int high)
    {        
        // Build a maxHeap
        for(int i = array.length / 2; i >= 0; i--)
        {
            percolateDown(array, i, array.length);
        }

        // Heap sort
        for(int i = array.length - 1; i > 0; i--)
        {
            swap(array, 0, i);
            percolateDown(array, 0, i);
        }
    }

As you can see, my method accepts low and high but does not currently do anything with those values. I have tried keep a boolean flag to determine when the algorithm is in range and to only sort when that boolean is true. But this did not work. If somebody could help me that would be greatly appreciated.

Thanks!

Advertisement

Answer

You could create new array with values in the given range only, then heapsort new array only. Then replace the elements of the original array.

User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement