Max Heap найти kth самых маленьких элементов

Question

Назначение:

У вас есть несортированный список элементов, в нашем случае целые числа, и вы должны найти k-й наименьший элемент в этом списке.Очевидная идея, конечно, состоит в том, чтобы отсортировать список в порядке возрастания и вернуть k-й наименьший элемент.Это должно быть сделано в O (N Log N).

Я пытаюсь найти k-й наименьший элемент, для которого я использую Max Heap.Как я понимаю, мне нужно отсортировать массив в порядке возрастания и вернуться, когда я получу k-й наименьший элемент.Если я правильно понимаю, максимальную кучу лучше всего использовать для сортировки массива в возрастающем порядке, но минимальную кучу для нахождения k-го наименьшего элемента.Это где не получить это.Как я могу отсортировать массив в порядке возрастания, а также вернуть kth мин?У меня проблема с поиском, как получить k-й наименьший элемент, если я использую Max Heap, так как не имеет смысла ждать, пока массив будет полностью отсортирован, затем обойти его циклом for и получить k-й наименьшийне будет делать HeapSort O (N log N), поскольку для обхода массива потребуется другой цикл for.И если я использую кучу Min, это будет в порядке убывания.

Вот как Max Heap сортирует массив в порядке возрастания:

Max Heap сделан: [10,9, 8, 5, 1, 8, 3, 5, 5, 1] ​​

[9, 5, 8, 5, 1, 8, 3, 1, 5, 10]

[8, 5, 8, 5, 1, 5, 3, 1, 9, 10]

[8, 5, 5, 5, 1, 1, 3, 8, 9, 10]

[5, 5, 5, 3, 1, 1, 8, 8, 9, 10]

[5, 3, 5, 1, 1, 5, 8, 8, 9, 10]

[5, 3, 1, 1, 5, 5, 8, 8, 9, 10]

[3, 1, 1, 5, 5, 5, 8, 8, 9, 10]

[1, 1, 3, 5, 5, 5, 5, 8, 8, 9, 10]

[1, 1, 3, 5, 5, 5, 8, 8, 9, 10]

Я не могу понять, как получить k-е наименьшее.Я думаю о Min Heap, потому что наименьший всегда индекс 0, но что используется для создания уменьшающегося массива?

Это мой метод, который является Heapsort.Он вызывает buildHeap, а затем выполняет сортировку.

//Find kth smallest element-----------------------------------------------------------------------------------------
private int[] findKthSmallestElement(int[] arr, int kthElement) {
    buildheap(arr);
    System.out.println("Max Heap is made: " + Arrays.toString(arr));

    if(kthElement > arr.length){
        System.out.println("Number does not exist.");
        return arr;
    }
    else if(kthElement == arr.length){
        System.out.println(kthElement + " st/nd/th smallest element number" + " is: " + arr[0]);
        return arr;
    }

    heapSize = arr.length - 1;

    for(int i = heapSize; i > 0; i--) {

        swapCurrentNodeWithMaxChild(arr,0, i);

        heapSize--;

        percolateDown(arr, 0,heapSize);

        System.out.println(Arrays.toString(arr));
    }

    return arr;
}

Answer 1

Я пытаюсь найти k-й наименьший элемент в Max Heap. Как я понимаю, мне нужно отсортировать массив в порядке возрастания и вернуться, когда я получу k-й наименьший элемент.

Нет, чтобы найти k-тый элемент smalls в Max Heap, нам просто нужно извлечь n-k элементов из Max Heap. Сортировка не требуется.

это не сделает HeapSort O (N log N), поскольку для обхода массива потребуется еще один цикл for.

Нам не нужно сортировать массив, но, как примечание стороны, один цикл обхода массива ничего не меняет, поскольку O(N log N + N) == O(N log N)

Answer 2

Вам нужно явно реализовать алгоритмы или вы можете использовать API Java? Если вы можете использовать API, это легко сделать с помощью Arrays.sort (). Я опускаю условия тестирования k

public void khtElement(k){
    int[] elements = new int[]{10, 9, 8, 5, 1, 8, 3, 5, 5, 1};

    Arrays.sort(elements);
    System.out.println(elements[k-1]);
}

Answer 3

Если k мало по отношению к размеру кучи N, то извлечение k-го наименьшего из Макс. Куча - довольно длинная задача - требуется O((N-k)*logN)~O(N*logN) время для (N-k) извлечения верхние элементы.

Для решения самой проблемы - чтобы получить k-наименьшее из несортированного списка, вам не нужна полная сортировка, не нужно создавать полную кучу.

Вариант 1) Получить k первых элементов, сборка max -heap только для этих k элементов . Пройдите через все остальные элементы. Если текущий элемент меньше верхнего кучи, удалите верх и вставьте текущий элемент. В конце кучи вершина содержит k-наименьшее. Сложность N*logK.

Полагаю, этот вариант предпочтительнее, если вы сейчас изучаете кучу.

Вариант 2) Выполнить алгоритм QuickSelect (средняя сложность линейная, но может возникнуть худший случай)