java - 我如何用 java 编写这个称为堆选择的算法？

Question

它应该像这样工作:

它应该使用两个最小堆，称为 H1 和 H2。 H1 是根据输入 vector 构建的，以后不应修改。 H2 最初只有一个节点，即 H1 的基数。在第 i 次迭代中，对于从 1 到 k-1 的 i，算法应提取 H2 的基数，该基数对应于 H1 中的 xi 节点，并且应在 H2 中重新插入 H1 堆中 xi 后面的节点。经过 k-1 次迭代后，H2 的基数应对应于输入 vector 的第 k^ 个最小元素。

这是我到目前为止所拥有的，但它不起作用。

public class HeapSelect { 

  public static void main(String args[]) { 

    List <Integer> intList=new ArrayList<Integer>();
    Scanner scanner = new Scanner(System.in);
    String[] strNums = null;
    if (scanner.hasNextLine()) {
        strNums = scanner.nextLine().split(" ");
    }
    if (strNums != null) {
        for (String strNum: strNums) {
            try {
                intList.add(Integer.parseInt(strNum.trim()));
            } catch (Exception e) {
                System.out.println("Invalid input");
                break;
            }
        }
    }


    int[] arr= new int[intList.size()];
    int index = 0;
    for(int i : intList){
        arr[index] = i;
        index++;
    }

    int k = scanner.nextInt();

    int n = arr.length; 

    MinHeap H1 = new MinHeap(n+1); 

    for (int i=0; i < n; i++) {
        H1.insert(arr[i]);
    }

    H1.minHeap();

    MinHeap H2 = new MinHeap(n+1); 
    H2.insert(H1.Heap[1]);

    for (int j=1; j <= k - 1; j++) {
        for (int i=j+1; i <= n; i++) {
            H2.insert(H1.Heap[i]);
        }
        H2.remove();
    }
    System.out.println("result " + H2.remove());
} 

}

Answer 1

正如您的算法所示，在倒数第四行，您需要从 H1 中删除，而不是从 H2 中删除。同时删除内部循环，将插入语句带到外部循环。否则，您只是添加和删除 H1 的顶部，而不会超出最小元素。最后，打印 H1.remove() 以获得第 k 个最小的整数。

也许你已经解决了这个问题，但是你可以只用一堆来完成。将所有元素插入到 minheap 中。要找到 k 个最小整数，只需将根整数取出 k 次放入整数数组/列表中即可。之后报告列表(答案)中的所有内容。如果你想恢复堆，只需将列表整数塞回去即可。堆生成的时间复杂度为 O(n)，k.log(n) 即可获取结果。如果您想要最大 k 个元素，请从 maxheap 开始。