Как реализовать сортировку минимальной кучи, чтобы найти k-й наименьший элемент? - PullRequest
Новая
       22

Как реализовать сортировку минимальной кучи, чтобы найти k-й наименьший элемент?

5 голосов
/ 10 апреля 2011

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

  • heapify массив
  • удалить минимальное (root) k раз
  • вернуть k-й наименьший элемент в группе

У меня нет проблем с созданием минимальной кучи.Я просто не уверен, как правильно удалить минимальное количество раз k и успешно вернуть k-й наименьший элемент в группе.Вот что у меня есть: 

 bool Example::min_heap_select(long k, long & kth_smallest) const {
//duplicate test group (thanks, const!)
Example test = Example(*this);

//variable delcaration and initlization
int n = test._total ;
int i;

//Heapifying stage (THIS WORKS CORRECTLY)
for (i = n/2; i >= 0; i--) {
    //allows for heap construction
    test.percolate_down_protected(i, n);
}//for  


//Delete min phase (THIS DOESN'T WORK)  
for(i = n-1; i >= (n-k+1); i--) {


    //deletes the min by swapping elements
    int tmp = test._group[0];
    test._group[0] = test._group[i];
    test._group[i] = tmp;       

    //resumes perc down
    test.percolate_down_protected(0, i);        


}//for

    //IDK WHAT TO RETURN 
    kth_smallest = test._group[0];



void Example::percolate_down_protected(long i, long n) {

//variable declaration and initlization:    
int currPos, child, r_child, tmp;
currPos = i;
tmp = _group[i];
child = left_child(i);  

//set a sentinel and begin loop (no recursion allowed)
while (child < n) {

    //calculates the right child's position
    r_child = child + 1;

    //we'll set the child to index of greater than right and left children
    if ((r_child > n ) && (_group[r_child] >= _group[child])) {
        child = r_child;
    }
    //find the correct spot
    if (tmp <= _group [child]) {
        break;
    }

    //make sure the smaller child is beneath the parent
    _group[currPos] = _group[child];

    //shift the tree down
    currPos = child;
    child = left_child(currPos);
}

//put tmp where it belongs
_group[currPos] = tmp;
 }

Как я уже говорил, часть минимальной кучи работает правильно.Я понимаю, что мне делать - кажется, что легко удалить корень k раз, но после этого какой индекс в массиве я возвращаю ... 0?Это почти работает - оно не стоит при k = n или k = 1. Будем очень благодарны за то, чтобы k-й наименьший элемент был в любой помощи!

Ответы [ 2 ]

7 голосов
/ 10 апреля 2011

Единственный индекс массива, который имеет значение для пользователя, равен нулю, что является минимальным элементом. Таким образом, после удаления элементов k самый маленький элемент k будет равен нулю.

Вероятно, вам следует уничтожить кучу и вернуть значение, а не просить пользователя заняться самой кучей ... но я не знаю деталей назначения.

Обратите внимание, что стандартная библиотека C ++ имеет алгоритмы, помогающие с этим: make_heap, pop_heap и nth_element.

0 голосов
/ 23 сентября 2018

Я не даю подробного ответа, просто объясняю ключевые моменты получения k наименьших элементов в упорядоченном дереве с минимальной кучей.Подход использует списки пропуска.

  • Сначала сформируйте список пропусков узлов дерева с одним элементом - узлом, соответствующим корню кучи.1-й минимальный элемент - это просто значение, хранящееся в этом узле.
  • Теперь удалите этот узел и вставьте его дочерние узлы в правильное положение, чтобы поддерживать порядок значений.Этот шаг занимает O(logk) время.Второе минимальное значение - это значение первого узла в этом списке пропуска.

Повторяйте вышеуказанные шаги, пока не получите все k минимальных элементов.Общая сложность времени составит log(2)+log(3)+log(4)+... log(k) = O(k.logk).Формирование кучи занимает время n, поэтому общая сложность времени составляет O(n+klogk).

Существует еще один подход без создания кучи Быстрый выбор , который имеет среднюю сложность по времени O (n), но наихудший случай как O(n^2).

Поразительное различие между этими двумя подходами состоит в том, что первый подход дает всем k элементам минимум до k-го минимума, тогда как quickSelect дает только k-й минимум элемента.При использовании первого подхода к памяти используется O(n) дополнительное пространство, которое quickSelect использует O(1).

...