Answer to Question #200996 in Java | JSP | JSF for Zahra

Question

HeapSort a given array with constant space complexity O(1).

Answer 1

public class Sort {

    public void heapSort(int[] a, int size) {
        buildMaxHeap(a);
        int HSize = size;
        for (int i = HSize - 1; i >= 1; i--) {
            int tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            HSize--;
            maxHeapify(a, 0, HSize);
        }
    }
    
    public void maxHeapify(int[] a, int i, int HSize) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest = i;
        if (left < HSize) {
            if (a[left] > a[i]) {
                largest = left;
            }
        }
        if (right < HSize) {
            if (a[right] > a[largest]) {
                largest = right;
            }
        }
        if (largest != i) {
            int tmp = a[i];
            a[i] = a[largest];
            a[largest] = tmp;
            maxHeapify(a, largest, HSize);
        }
    }
    
    public void buildMaxHeap(int[] a) {
        int HSize = a.length;
        for (int i = (HSize - 1) / 2; i >= 0; i--) {
            maxHeapify(a, i, HSize);
        }
    }
}