获取数组中的第 k 个最大元素 - 使用 maxheap 实现但在 leetcode 中超出时间

Question

我正在尝试解决这个 leetcode 挑战。我实现了 MaxHeap 并尝试弹出值以获取数组中的第 K 个最大元素，但我超出了时间限制。

我的 MaxHeap 实现是否有任何问题，它很慢，或者可以用更快的方法完成吗？

问题 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 1

你有一个无限循环，因为你对 left-child-index 和 right-child-index 使用了错误的公式。

看看heapifyDown。测试的第一个索引是0，getRightChildIndex()说对child也在0*2 == 0.

对于根在0的堆，i的左右children在i*2+1和i*2+2。对于根位于 1 的堆（不是你的情况），i 的左右 children 位于 i*2 和 i*2+1.

请注意，如果您解决了这个问题，那么您的算法就可以工作，但效果不会很好。此问题的适当解决方案使用快速选择（预期 O(n)）、min-heap（O(n * log k)）或部分堆排序（O(n + k log n)）。你的就像部分堆排序，但在开始时没有 O(n) heapify，给出 O(n log n)。

获取数组中的第 k 个最大元素 - 使用 maxheap 实现但在 leetcode 中超出时间

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

java

data-structures

heapsort