Как использовать ArrayList в heapsort - PullRequest
Новая
       57

Как использовать ArrayList в heapsort

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

Я пытаюсь реализовать heapsort, используя ArrayList.Я не знаком с использованием ArrayList, но вот что я придумал для одного метода моей программы, maxHeap:

Я не уверен, правильно ли я использую метод array.get(element),Я знаю, что вы должны использовать этот метод для получения значения в элементе, но в этом случае, если бы я хотел установить largest = left, я бы поставил его как arr.get(largest) = arr.get(left)?Или я бы использовал метод array.set()? 

public class Heaps 
{
   public void maxHeap(ArrayList<Integer> arr, int index, int size)
   {

    int largest = index;            // Largest index
    int left = (2*index) + 1;       // Left Child node
    int right =(2*index) + 2;       // Right Child node
    size = arr.size();              // Size of array                        

    if ((left < size) && (arr.get(left) > arr.get(largest)))
        {               
            largest = left;
        }
    else 
        {
            largest = index;                    
        }
    if ((right < size) && (arr.get(right) > arr.get(largest)))  
        {
            largest = right;
        }
    if (largest != index)                       
        {   
           // Swap element at index with element at largest
            Collections.swap(arr, arr.get(index), arr.get(largest));
            maxHeap(arr, largest, size);        // Recursive call
        }
    }


  public static void main(String[] args)
{
    Heaps h = new Heaps();

    int n = 5;

    ArrayList<Integer> array = new ArrayList<Integer> (n);

    Integer a[] = new Integer[n];
    for (int i = 0; i < n; i++) 
    {
        array.add(a[i]);
    }


    array.add(0, 30);
    array.add(1, 10);
    array.add(2, 16);
    array.add(3, 17);
    array.add(4, 19);

    h.maxHeap(array, 0, array.size());
    System.out.print(array);


    }
}

Вывод этого должен быть максимальной кучей значений, например: 30, 19, 17, 16, 10 Фактический вывод - тот же самый введенный массив: 30, 10, 16, 17, 19 Итакв основном, maxHeap не работал.Я не уверен, что мой синтаксис неверен для метода maxHeap.

1 Ответ

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

Я бы порекомендовал не приближаться к сложной проблеме, если вы не использовали ArrayList в прошлом.Используя этот урок Я исправил ваш код. 

public static class Heaps { // Static class so you can access it through the main class.

    public void maxHeap(ArrayList<Integer> array, int index, int size) {

        int largest = index; // Root Node
        int left = 2 * index + 1; // Left Child node
        int right = 2 * index + 2; // Right Child node

        if (left < size && array.get(left) > array.get(largest)) {
            largest = left;
        }
        if (right < size && array.get(right) > array.get(largest)) {
            largest = right;
        }

        if (largest != index) {
            Collections.swap(array, index, largest); // Swap the indexes not the values
            maxHeap(array, largest, size);
        }

    }

}

public static void main(String[] args) {

    Heaps h = new Heaps(); // Not edited, but I would recommend static methods for this example

    ArrayList<Integer> array = new ArrayList<Integer>();

    // Arrays are automatically resized, no need to make an empty array, etc.

    array.add(30);
    array.add(10);
    array.add(16);
    array.add(17);
    array.add(19);
    array.add(50);
    array.add(70);
    array.add(86);
    array.add(7);
    array.add(-2);

    int size = array.size();

    // Prerequisites for max heap sorting.

    for(int i = size / 2 - 1; i >= 0; i--) {
        h.maxHeap(array, i, size);
    }

    for(int i = size - 1; i >= 0; i--) {
        Collections.swap(array, i, 0);
        h.maxHeap(array, 0, i);
    }

    System.out.print(array);
    // Output: [-2, 7, 10, 16, 17, 19, 30, 50, 70, 86]
    // Time: 284549 nanoseconds

}
...