在堆排序中弹出 3 个元素

Question

如果我还想找到第三大元素，然后弹出3，我该如何实现？

package cs.ds.main;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class HeapSort {

    public static void main(String[] args) {
        // TODO code application logic here
        System.out.println("New Heapsort");
        long startTime = System.currentTimeMillis();
        
        int[] arr = generateNonRedundantData(100);
        //int[] arr = {9,5,8,4,1,6,2};
        
        System.out.println("Original array:");
        display(arr);
        doublePopHeapsort(arr);

        System.out.println("Sorted array:");
        display(arr);
        
        long endTime = System.currentTimeMillis();
        
        long elapsedTime = endTime - startTime;
        
        System.out.print("Elapsed Time: " + elapsedTime);
    }
    
    public static void doublePopHeapsort(int[] arr) {
        int n = arr.length;

        if (n <= 1) return;

        buildMaxHeap(arr, n);

        /* Grabs 2 largest numbers in maxheap each pass */
        while (--n > 2) {
            swap(arr, 0, n);
            --n;
            if (arr[1] >= arr[2]) {
                swap(arr, 1, n);
                heapify(arr, n, 1);
            } else {
                swap(arr, 2, n);
                heapify(arr, n, 2);
            }
            heapify(arr, n, 0);
        }

        /* regular heapsort to handle no more than 3 unsorted elements. */
        do {
            swap(arr, 0, n);
            heapify(arr, n, 0);
        } while (--n > 0);
    }

    public static void buildMaxHeap(int[] arr, int n) {
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;

        if (left < n && arr[left] > arr[max]) {
            max = left;
        }

        if (right < n && arr[right] > arr[max]) {
            max = right;
        }

        if (max != i) {
            swap(arr, i, max);
            heapify(arr, n, max);
        }
    }


    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static int[] generateNonRedundantData(int size) {
        int[] arr = new int[size];
        Set<Integer> uniqueValues = new HashSet<>();
        Random rand = new Random();

        for (int i = 0; i < size; i++) {
            int value;
            do {
                value = rand.nextInt(size);
            } while (!uniqueValues.add(value)); // Ensure unique values

            arr[i] = value;
        }

        return arr;
    }
    
    public static void display(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

我尝试过，但每次都会出错。

Answer 1

最大堆中的第三大堆可以位于 6 个不同的索引处。如果第二大的在右侧（索引 2 处），那么它的两个孩子都是候选者（索引 5 和 6 处），而且也是其兄弟姐妹（索引 1 处）。当第二大的位于左侧（索引 1 处）时，我们在索引 2、3 和 4 处得到另外 3 个候选者。

这也意味着，如果您的堆的节点少于 7 个，您需要防止使用这些候选索引进行超出范围的访问。

此外，在某些情况下，第三大元素位于接近数组末尾的索引处，它可能会（意外地）被想要将最大或第二大元素移出堆的交换所交换分割。您还需要防止此类不需要的突变。

为了避免这些复杂性，当数组变得足够小以进入这种情况时，最好退出主循环。所以我建议设置循环条件

n > 8

。这样上述边界条件就不会发生。最后，您将得到一个大小为 8 或更小的堆，可以使用标准方法对其进行排序，或者（如果您愿意）使用 double pop 方法进行排序，直到该堆也用完为止。

这是建议的代码：

    public static void triplePopHeapsort(int[] arr) {
        int n = arr.length;

        if (n <= 1) return;

        buildMaxHeap(arr, n);

        while (n > 8) {
            // Determine the indices of the 2dn and 3rd greatest values:
            int i = arr[1] >= arr[2] ? 1 : 2;
            int j = i == 1
                ? (arr[2] >= arr[3]
                    ? (arr[2] >= arr[4] ? 2 : 4)
                    : (arr[3] >= arr[4] ? 3 : 4)
                )
                : (arr[1] >= arr[5]
                    ? (arr[1] >= arr[6] ? 1 : 6)
                    : (arr[5] >= arr[6] ? 5 : 6)
                );
            swap(arr, 0, --n);
            swap(arr, i, --n);        
            swap(arr, j, --n);
            heapify(arr, n, j);
            heapify(arr, n, i);
            heapify(arr, n, 0);
        }

        while (n > 1) {
            swap(arr, 0, --n);
            heapify(arr, n, 0);
        }
    }