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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.