How should I solve my heap select problem?

Question

I'm trying to find the k-th smallest element in a unordered array. I should use two min-heaps h1, h2 where the first one has all the array keys and the second one has h1's root as the only element. The algorithm should iterate k-1 times and on every iteration h2's root is extracted and his corresponding children on the first heap should be inserted in h2. Doing so on the kth iteration my desired element it will be the root of the second heap. The algorithm complexity should be O(n+k*logk) cause it takes linear time to initialize the heap and inserting k elements on a heap takes O(k*logk).

Elements on the input can be repeated multiple times, so it happens that with certain inputs my program gets stuck on a loop where it keeps inserting on h2 the same children. For example, if I extract a node with key=5 and the same node on h1 has two children with keys equal to 5 and 8, it inserts 5 and 8 on h2 but the next iteration where I extract 5 it keeps inserting 5 and 8.

I already tried to solve it by inserting indexes of nodes on h2 instead of their keys but it didn't work.

How should I solve this problem?

 import java.util.Arrays;

    public class Heap_Select extends Select_algorithms {
        public Integer select(Integer[] array) {
            Integer kthElement = array[array.length - 1];
            Integer[] inputArray = Arrays.copyOfRange(array, 0, array.length - 1);
            Heap H1 = new minHeap(inputArray);
            Heap H2 = new minHeap(new Integer[]{0});
            return heap_select(H1, H2, kthElement);
        }
    
        public static Integer heap_select(Heap h1, Heap h2, Integer kthElement){
            Integer searchValue, leftPosition, leftChild, rightPosition, rightChild;
    
            if(kthElement >= 0 && kthElement < h1.heapsize()){
                for (int i = 0; i < kthElement; i++){
                    searchValue = h2.extractRoot();

                    leftPosition = h1.left(searchValue);
                    rightPosition = h1.right(searchValue);
    
                    if (leftPosition < h1.heapsize() - 1) {
                        h2.insert(leftPosition);
                        h2.insert(rightPosition);
                    }
                }
            }
            else
                System.out.println("Value out of range");
    
            Integer result = h2.getMin();
            return h1.getValueAtPos(result);
        }
    }

Answer 1

The solution is to store indexes as well as values in the auxiliary heap. Here is how it can be done in Python:

import heapq

def heapselect(x, k):
    """Return k-th smallest element of x"""
    heapq.heapify(x)
    s = [(x[0], 0)] #auxiliary heap
    for _ in range(k-1):
        ind = heapq.heappop(s)[1]
        if 2*ind+1 < len(x):
            heapq.heappush(s, (x[2*ind+1], 2*ind+1))
        if 2*ind+2 < len(x):
            heapq.heappush(s, (x[2*ind+2], 2*ind+2))
    return s[0][0]