1
\$\begingroup\$

Here is my working code for a min-heap sort using an Array-List. I would like any input as to areas that need additional refining and any areas that are against proper formatting/usage. Although not defined, I was attempting to use an array implementation instead of the Array-List collection as the class has been creating your own implementations of collections rather than using the collections. I struggled some and reverted to the collection as it is about the heap implementation rather than array/Array-List. The one area that I feel may be incorrect is the output. It is in a fully sorted order rather than what I was expecting IE:

expected: B, H, F, L, T, G, S, S, M, V actual: B, F, G, H, L, M, S, S, T, V

expected: 1, 2, 5, 3, 3, 7, 6, 9, 4, 6 actual: 1, 2, 3, 3, 4, 5, 6, 6, 7, 9

Here is my code:

import java.util.ArrayList;

final class Heap<T extends Comparable<T>> {
private final ArrayList<T> heapArray = new ArrayList<>();

public Heap() {

}

public Heap(T[] objects) {
    for (T object : objects) {
        add(object);
    }
}


public void add(T newObject) {
    heapArray.add(newObject);
    int currentIndex = heapArray.size() - 1;

    while (currentIndex > 0) {
        int parentIndex = (currentIndex - 1) / 2;

        if (heapArray.get(currentIndex).compareTo(heapArray.get(parentIndex)) > 0) {
            T temp = heapArray.get(currentIndex);
            heapArray.set(currentIndex, heapArray.get(parentIndex));
            heapArray.set(parentIndex, temp);
        } else {
            break;
        }

        currentIndex = parentIndex;
    }
}

public T remove() {
    if (heapArray.isEmpty()) {
        return null;
    }

    T removedObject = heapArray.get(0);
    heapArray.set(0, heapArray.get(heapArray.size() - 1));
    heapArray.remove(heapArray.size() - 1);

    int currentIndex = 0;
    while (currentIndex < heapArray.size()) {
        int leftChildIndex = 2 * currentIndex + 1;
        int rightChildIndex = 2 * currentIndex + 2;

        if (leftChildIndex >= heapArray.size()) {
            break;
        }

        int maxIndex = leftChildIndex;

        if (rightChildIndex < heapArray.size()) {
            if (heapArray.get(maxIndex).compareTo(heapArray.get(rightChildIndex)) < 0) {
                maxIndex = rightChildIndex;
            }
        }

        if (heapArray.get(currentIndex).compareTo(heapArray.get(maxIndex)) < 0) {
            T temp = heapArray.get(maxIndex);
            heapArray.set(maxIndex, heapArray.get(currentIndex));
            heapArray.set(currentIndex, temp);
            currentIndex = maxIndex;
        } else {
            break;
        }
    }

    return removedObject;

}

public int getSize() {
    return heapArray.size();
}
}

public class HeapSort {

public static <T extends Comparable<T>> void heapSort(T[] list) {

    Heap<T> heap = new Heap<>();

    for (T list1 : list) {
        heap.add(list1);
    }

    for (int i = list.length - 1; i >= 0; i--) {
        list[i] = heap.remove();
    }

}

public static void main(String[] args) {

    Integer[] Test1 = {9, 7, 6, 3, 4, 6, 5, 1, 2, 3};
    heapSort(Test1);

    for (Integer Test11 : Test1) {
        System.out.print(Test11 + " ");
    }

    System.out.println();

    Character[] Test2 = {'L', 'F', 'G', 'S', 'V', 'B', 'S', 'M', 'H', 'T'};
    heapSort(Test2);

    for (Character Test21 : Test2) {
        System.out.print(Test21 + " ");
    }

}
}
\$\endgroup\$
1

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.