HeapSort возвращает неправильный массив (Java) - PullRequest
Новая
       84

HeapSort возвращает неправильный массив (Java)

0 голосов
/ 12 октября 2018

My HeapSort возвращает массив, который находится не в правильном порядке.Мой исходный массив {15, 9, 11, 5, 6, 7}, и при запуске метода heapSort я получаю этот массив: {15, 11, 9, 6, 7, 5}.

Я напечатал метод, чтобы увидеть, что сделал и получил maxHeap: {15, 9, 11, 5, 6, 7}, который при отображении в двоичном дереве на самом деле является maxHeap.Это заставляет меня поверить, что что-то не так с методом сортировки или методом buildMaxHeap. 

    public class heaps
    {
    public void maxHeap(int arr[], int index, int n)
    {
    int largest = index;
    n = arr.length;
    int l = (2*index) + 1;
    int r =(2*index) + 2;
    int size = arr.length;                                  

    if ((l < n) && (arr[l] > arr[largest]))             
        {
            largest = l;
        }
    else 
        {
            largest = index;    
        }
    if ((r < size) && arr[r] > (arr[largest]))          
        {
            largest = r;
        }
    if (largest != index)
        {
            int temp = arr[index];
            arr[index] = arr[largest];
            arr[largest] = temp;
            maxHeap(arr, largest, n);
        }
}

public void buildMaxHeap(int arr[])
{
    int n = arr.length; 
    for (int index = (n / 2) - 1; index >= 0; index--)
    {
        maxHeap(arr, index, n);
    }
}

public void sort(int arr[])
{
    int n = arr.length;
    buildMaxHeap(arr);

    for (int index = n - 1; index >= 0; index--)
    {
        int temp = arr[0];
        arr[0] = arr[index];
        arr[index] = temp;
        n = n - 1;                      
        maxHeap(arr, index, 0);
    }   
}

public void printArray(int arr[]) 
{ 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
        System.out.print(arr[i]+" "); 
    System.out.println(); 
}

 public static void main(String[] args)
{
    heaps o = new heaps();

    int array[] = {15, 9, 11, 5, 6, 7};

    heaps.sort(array);
    heaps.printArray(array);
    heaps.maxHeap(array, 0, array.length);
    heaps.printArray(array);
}      
}

1 Ответ

0 голосов
/ 13 октября 2018

Если я правильно понимаю ваш метод maxHeap, параметр n должен быть максимальным индексом.То есть maxHeap(arr, index, n) должен взять элемент на arr[index] и опустить его в кучу, но не дальше, чем arr[n].

Если это так, то ваша ошибка во второй строке вашего maxHeap method: 

n = arr.length;

Вы перезаписываете значение переданного вами параметра n.

У вас есть этот вызов в вашем методе sort: 

    maxHeap(arr, index, 0);

Итак, вы говорите maxHeap толкнуть предмет на arr[index] вниз, но не ниже arr[0].Мне кажется, это будет проблемой, потому что ничего не будет двигаться.

Вам нужно потратить немного времени на тщательное изучение вашего кода.Один шаг с отладчиком - отличная помощь.Если вы не знаете, как использовать отладчик, сейчас самое подходящее время для изучения.

...