k-й наименьший элемент с использованием min-heap - PullRequest
Новая
       17

k-й наименьший элемент с использованием min-heap

0 голосов
/ 17 января 2019

Я решал проблему k-го наименьшего элемента, используя min-heap, но застрял, так как он всегда дает мне первый наименьший элемент, поэтому я предполагаю, что моя функция extractmin работает неправильно. Мой подход состоял в том, чтобы превратить массив в min-кучу структура данных, в которой root является минимальным элементом, а затем удаляет k-1 наименьших элементов, а затем просто возвращает значение root. 

#include <iostream>

using namespace std;

void swap(int &x, int &y)
{
    int u = x;
    x = y;
    y = u;
}

int l(int p)
{
    return 2 * p + 1;
}

int r(int p)
{
    return 2 * p + 2;
}

void heapify(int arr[], int i, int n);

void makeheap(int arr[], int n)
{
    int last = n - 1;
    for (int i = (last - 1) / 2; i >= 0; i--)
    {
        heapify(arr, i, n);
    }
}

void heapify(int arr[], int i, int n)
{
int smallest = arr[i],y=0;
if (l(i) <= n - 1 && arr[l(i)] < arr[i])
{
    smallest = arr[l(i)];
}
if (r(i) <= n - 1 && arr[r(i)] < smallest)
{
    smallest = arr[r(i)];
 y=1;
}
if (smallest != arr[i])
{ 
    if(y==0){
    swap(arr[l(i)], arr[i]);}
    else if(y==1)
    {
        swap(arr[r(i)],arr[i]);
    }
    heapify(arr, i, n);
}
}

void extractmin(int arr[], int &n)
{
    swap(arr[0], arr[n - 1]);
    n--;
    heapify(arr, 0, n);
}

int getmin(int arr[])
{
    return arr[0];
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        int arr[n];
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
        int k;
        cin >> k;
        makeheap(arr, n);
        for (int i = 0; i < k - 1; i++) {
            extractmin(arr, n);
        }

        cout << getmin(arr) << "\n";
    }
}

Введите: 

2
6
7 10 4 3 20 15
3
5

7 10 4 20 15
4

Ожидаемый результат: 

7
15

Мой вывод: 

3
4

1 Ответ

0 голосов
/ 17 января 2019

В heapify () вы используете 

swap(smallest,arr[i]);

Это меняет значения в наименьшее и arr [i]. Но arr [l (i)] или arr [r (i)] не изменяется. На самом деле это копирует меньшее значение arr [l (i)] и arr [r (i)] в arr [i].

Также в основном вы делаете 

for (int i = 0; i < k - 1; i--) {

, который считает меня до тех пор, пока не достигнет INT_MIN вместо того, чтобы считать до k. Это быстро приводит к тому, что куча становится пустой, а код перестаёт работать.

PS: почему бы не использовать std :: make_heap и друзей?

...