get kth-largest-element-in-an-array – implemented using maxheap but getting time exceeded in leetcode

I am trying to solve this leetcode challenge . I implemented a MaxHeap and tried to popout the values to get the Kth largest element in the array but I get a time limit exceeded.

Is there any issue with my MaxHeap implementation that it is slow or can this be done in a faster method?

Problem https://leetcode.com/problems/kth-largest-element-in-an-array/

class Solution {

private int capacity = 10;
private int size = 0;
int items [] = new int[capacity];

//parent = (i-1)/2
//left-child = 2i+1
//right-child = 2i


 public int findKthLargest(int[] nums, int k) {        
    for(int i=0;i<nums.length;i++){
        push(nums[i]);
    }

    //printHeapArray();
    for(int i=0; i<k-1; i++){
        int val = pop();
        System.out.println("max val popped" + val);
      //  printHeapArray();
    }
    return peek();
}


private int getLeftChildIndex(int index){
    return index*2+1;
}

private int getRightChildIndex(int index) {
    return index*2;
}

private int getParentIndex(int index) {
    return (index-1)/2;
}

private int leftChild(int index) {
    return items[getLeftChildIndex(index)];
}

private int rightChild(int index) {
    return items[getRightChildIndex(index)];
}

private int parent(int index) {
    return items[getParentIndex(index)];
}

private boolean hasParent(int index){
    return getParentIndex(index) >= 0;
}

private boolean hasLeftChild(int index){
    return getLeftChildIndex(index) < size;
}

private boolean hasRightChild(int index){
    return getRightChildIndex(index) < size;
}

private void swap(int indexOne, int indexTwo) {
    int temp = items[indexOne];
    items[indexOne] = items[indexTwo];
    items[indexTwo] = temp;
}

private void ensureCapacity() {
    if(capacity == size -1) {
        items = Arrays.copyOf(items, capacity*2);
        capacity *= 2;
    }
}

public int peek() {
    if(size == 0) {
        throw new IllegalStateException();
    }
    return items[0];
}

public void push(int item) {
    ensureCapacity();
    items[size] = item;
    size++;
    heapifyUp();
}

private void heapifyUp() {
    int index = size - 1;
    while(hasParent(index) && parent(index) < items[index]) {
        swap(getParentIndex(index), index);
        index = getParentIndex(index);
    }
}

public int pop() {
    if(size == 0 ) throw new IllegalStateException();
    int item = items[0];
    items[0] = items[size-1];
    size--;
    heapifyDown();
    return item;
}



//1.Compare the children first and find the child you want to compare against with parent
//2.Compare the selected child with its parent to see if it needs to be swapped
private void heapifyDown() {
    int index = 0;
    while(hasLeftChild(index))
    {
        int smallerChildIndex = getLeftChildIndex(index);
        if(hasRightChild(index) && rightChild(index) > leftChild(index)){
            smallerChildIndex = getRightChildIndex(index);
        }
        if(items[index] > items[smallerChildIndex]) {
            break;
        }

        if(items[smallerChildIndex] >  items[index]) {
            swap(smallerChildIndex, index);
        }
        index = smallerChildIndex;

    }
}


public void printHeapArray(){
    System.out.println(Arrays.toString(items));
}

}

Answer

You have an infinite loop, because you’re using the wrong formulas for left-child-index and right-child-index.

Look at heapifyDown. The first index tested is 0, and getRightChildIndex() says that it’s right child is also at 0*2 == 0.

For heaps with the root at 0, the left and right children of i are at i*2+1 and i*2+2. For heaps with the root at 1 (not your case), the left and right children of i are at i*2 and i*2+1.

Note that if you fix this then your algorithm can work, but it won’t be awesome. Appropriate solutions for this problem use quickselect (expected O(n)), a min-heap (O(n * log k)), or a partial heapsort (O(n + k log n)). Yours is like a partial heap sort, but without the O(n) heapify at the start, giving O(n log n).

Advertisement

Answer