Правильные условия для тройного дерева Heapsort - PullRequest
Новая
       18

Правильные условия для тройного дерева Heapsort

0 голосов
/ 24 марта 2019

Я пытаюсь отсортировать массив с помощью троичного дерева Heapsort, и я знаю, что условия в этом методе - проблема. Я не знаю, как изменить это, чтобы быть правильным.

Во время отладки я вижу, что алгоритм перезаписывает свою прошлую работу. У меня есть несколько условий с модулем, чтобы число детей всегда было правильным. Родитель троичного дерева может иметь до 3 детей, но если у него только 1 или 0, я хотел бы получить правильное количество сравнений. 

private static void sink(int[] a, int k, int size)
    {
        // runs until the k value can't exist, i.e., no children
        while (3*k-1 <= size)
        {
            // j is the leftmost child of k
            // -1 to access left node, another -1 for array access
            int j = 3*k-2;
            //alternating between trying j or (3*k-1)
            if ((j) % 3 == 0)
            {
                if (j < size && a[j] < a[j+1])
                    j++;
            }
            // runs if the parent node k has 3 children
            else if((j) %3 == 1)
            {
                // checking left and middle node
                if (j < size && a[j] < a[j+1])
                {
                    j++;
                    // checking middle and right node
                    if (a[j] < a[j+1])
                        j++;
                }
                // checks left and right node
                else if (j < size && a[j] < a[j+2])
                    j+=2;
            }
            /*
                exchanges child if parent is smaller
            */
            if (!(a[k-1] < a[j]))
                break;
            int temp = a[k-1];
            a[k-1] = a[j];
            a[j] = temp;
            k = j;
        }
    }

С массивом размера семь, вывод: 

Before Sorting:
[7, 2, 3, 6, 5, 4, 1]
After Sorting:
[2, 4, 3, 1, 5, 6, 7]
...