如何在java中编写这个叫做堆选择的算法？

Question

它的工作原理应该是这样的。

它应该使用两个最小堆，分别叫H1和H2. H1是根据输入的向量建立的，以后不应该再修改。H2最初只有一个节点，即H1的半径。在第i^次迭代时，对于从1到k-1的i，算法应该提取H2的radix，对应H1中的xi节点，它应该将H1 Heap中xi后面的节点重新插入到H2中。经过k-1次迭代后，H2的radix应该对应t输入向量的第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()for kth最小的int。

也许你已经解决了，但你可以只用一个堆来解决。将所有的元素插入到minheap中。要想找到第k个最小的整数，只要把根整数取出来k次，变成一个整数数组list。之后在list(answer)中报出你的任何内容。如果你想恢复堆，只要把list整数塞回去就可以了。用O(n)做堆，用k.log(n)得到结果。如果你想要最大的k元素，就从maxheap开始。