How can I code this algorithm, called Heap Select, in java?

Question

It should work like this:

It should use two min-heap, called H1 and H2. H1 is built based on the input vector and it should not be modified later on. H2 initially has only one node, H1's radix. At the i^th iteration, for i that goes from 1 to k-1, the algorithm should extract H2's radix, which corresponds to a xi node in H1, and it should reinsert in H2 the nodes that follow xi in H1 Heap. After k-1 iterations H2's radix should correspond t the k^th smallest element of the input vector.

This is what I have so far, but it does not work.

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

As your algorithm reads, on fourth last line, you need to remove from H1, not H2. Also remove the inner loop, take the insert statement to outer loop. Otherwise you’re just adding and removing top of H1 not going anywhere beyond the smallest element. And in the end, print H1.remove() for kth smallest int.

Maybe you’ve solved it already, but you can do it with just one heap. Insert all the elements into the minheap. To find the k smallest integers, just take out the root integers k times into a integer array/list. After that report whatever you have in list(answers). If you want to restore the heap, just jam the list integers back in. O(n) for heap making, and k.log(n) to get the results. If you want maximum k elements, start with maxheap.