给定范围内的堆排序

Question

我正在尝试编写一个 Heapsort 方法，该方法仅在传递给该方法的给定范围内执行排序。传入范围 low 和 high，这些值对应于堆内的值，而不是堆的索引。例如，输入数组可能是：28 10 49 20 59 61 17，如果 low = 49 和 high = 61，堆排序后的结果数组将如下所示：28 10 20 49 59 61 17。范围保持不变。我已经有一个可用的 Heapsort 方法，但我的问题是如何修改此方法以在传递的范围内进行排序？

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

如您所见，我的方法接受低值和高值，但目前不对这些值执行任何操作。我曾尝试保留一个布尔标志来确定算法何时在范围内，并且仅在该布尔值为真时才进行排序。但这没有用。如果有人可以帮助我，将不胜感激。

谢谢！

Answer 1

您可以仅使用给定范围内的值创建新数组，然后仅对新数组进行堆排序。然后替换原数组的元素。

Answer 2

public static void main( String [ ] args ) {
        Integer[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        heapsort(arr, 0, 4);
}

/**
 * Standard heapsort.
 * @param a an array of Comparable items.
 */
public static <AnyType extends Comparable<? super AnyType>> void heapsort(AnyType [ ] a, int low, int high) {
    for (int i = high / 2; i >= low; i--)  /* buildHeap */
        percDown( a, i, high);
    for (int i = high; i > low; i--) {
        swapReferences(a, low, i);         /* deleteMax */
        percDown(a, low, i);
    }
    System.out.println(Arrays.toString(a));
}

给定范围内的堆排序

Heapsort Within a Given Range

java

sorting

algorithm

heap

heapsort