где неисправная логика в этой функции повторной кучи? - PullRequest
Новая
       8

где неисправная логика в этой функции повторной кучи?

0 голосов
/ 27 мая 2018

В настоящее время я работаю со структурой кучи, которая должна использоваться для сортировки чисел в массиве.Я сделал что-то подобное в коде, когда хочу отсортировать структуру, когда извлекаю (удаляю из очереди) элемент из кучи. 

template<typename T>
inline void dHeap<T>::reHeapDown(int root, int bottom)
{
    int minChild;
    int rightChild;
    int leftChild;
    int temp;



// Get index of root's right/left child
leftChild = root * 2 + 1;
rightChild = root * 2 + 2;

//Then we are not done with re-heaping
if (leftChild <= bottom)
{
    if (leftChild == bottom)
    {
        minChild = leftChild;
    }

    else
    {
        if (arr[leftChild] <= arr[rightChild])
            minChild = leftChild;
        else
            minChild = rightChild;
    }

    if (arr[root] > arr[minChild])
    {
        // Swap these two elements
        temp = arr[root];
        arr[root] = arr[minChild];
        arr[minChild] = temp;
        // Make recursive call till reheaping completed
        reHeapDown(minChild, bottom);
    }
}
}

Я думал, что самое низкое значение в куче всегда будетбыть в корне, и это значение, которое я буду вставлен (исключен) в моей функции поп.Но у меня возникла проблема с тем, что она не будет правильно сортировать кучу.что-то не так с моей логикой в ​​этой функции, и если да, то где это?

1 Ответ

0 голосов
/ 27 мая 2018

При построении кучи применяется только свойство:

  • в случае минимальной кучи каждый родительский элемент меньше своих потомков
  • в случае максимальной кучи каждый родительский элемент больше своих дочерних элементов.
  • в случае минимально-максимальной кучи четные уровни глубины (0,2,4 ..) меньше, а нечетные уровни (1,3,5 ...) больше, чем их соответствующие дочерние элементы.

Однако куча не обязательно будет отсортирована.Он будет сбалансированным, поскольку он заполняется по порядку, уровень за уровнем, слева направо.

Heapsort отсортирует массив с помощью функций кучи.Окончательный массив также будет работать как сбалансированная и отсортированная куча.

...