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 + " ");
}
}
}
return null;
in an OO paradigm. It's a wrong practice. – DrProgrammer Nov 22 '15 at 21:46