Heap Sorting

Given a unsorted array, heap sort transforms it into a descending sequence:

1. Convert the array into a max heap using heap insertion or heapify operations
2. Repeatedly swap the root element with the last position, reduce heap size, and re-adjust
3. Continue untill heap size reduces to zero

Heap Construction Methods

Forward Traversal with Heap Insertion (O(N log N))

for (int i = 0; i < data.length; i++) {
    insertHeap(data, i);
}

Reverse Traversal with Heapify (O(N))

for (int i = data.length - 1; i >= 0; i--) {
    heapify(data, i, data.length);
}

Heap Sort Implementation

public static void heapSort(int[] data) {
    if (data == null || data.length < 2) return;
    
    for (int i = 0; i < data.length; i++) {
        insertHeap(data, i);
    }
    
    int heapSize = data.length;
    swap(data, 0, --heapSize);
    
    while (heapSize > 0) {
        heapify(data, 0, heapSize);
        swap(data, 0, --heapSize);
    }
}

Extension: Sorting Nearly Ordered Arrays

For arrrays where elements move ≤ K positions when sorted (K ≪ N):

public static void sortNearlyOrdered(int[] data, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    int index = 0;
    
    for (; index <= Math.min(data.length - 1, k); index++) {
        minHeap.add(data[index]);
    }
    
    int i = 0;
    while (index < data.length) {
        minHeap.add(data[index++]);
        data[i++] = minHeap.poll();
    }
    
    while (!minHeap.isEmpty()) {
        data[i++] = minHeap.poll();
    }
}

Comparator Fundamentals

Comparators enable custom ordering by overriding comparison operators:

public int compare(T element1, T element2) {
    // Return negative: element1 comes first
    // Return positive: element2 comes first
    // Return zero: equal priority
}

Student ID Comparator Example

public static class StudentIdComparator 
    implements Comparator<Student> {
    
    @Override
    public int compare(Student s1, Student s2) {
        return s1.getId() - s2.getId();
    }
}

// Usage
Arrays.sort(students, new StudentIdComparator());

Custom Heap with Comparator

public class CustomHeap<T> {
    private ArrayList<T> elements;
    private HashMap<T, Integer> positionMap;
    private int size;
    private Comparator<? super T> comp;
    
    public CustomHeap(Comparator<? super T> comparator) {
        elements = new ArrayList<>();
        positionMap = new HashMap<>();
        size = 0;
        comp = comparator;
    }
    
    public void addElement(T item) {
        elements.add(item);
        positionMap.put(item, size);
        adjustUp(size++);
    }
    
    public T removeTop() {
        T top = elements.get(0);
        int last = size - 1;
        swap(0, last);
        positionMap.remove(top);
        adjustDown(0, --size);
        return top;
    }
    
    public void updateElement(T item) {
        Integer pos = positionMap.get(item);
        adjustUp(pos);
        adjustDown(pos, size);
    }
    
    private void adjustUp(int pos) {
        while (comp.compare(elements.get(pos), 
               elements.get((pos - 1) / 2)) > 0) {
            swap(pos, (pos - 1) / 2);
            pos = (pos - 1) / 2;
        }
    }
    
    private void adjustDown(int pos, int heapSize) {
        int leftChild = 2 * pos + 1;
        while (leftChild < heapSize) {
            int dominant = (leftChild + 1 < heapSize && 
                comp.compare(elements[leftChild + 1], elements[leftChild]) > 0) 
                ? leftChild + 1 : leftChild;
                
            dominant = comp.compare(elements[dominant], elements[pos]) > 0 
                ? dominant : pos;
                
            if (dominant == pos) break;
            swap(pos, dominant);
            pos = dominant;
            leftChild = 2 * pos + 1;
        }
    }
    
    private void swap(int i, int j) {
        T item1 = elements.get(i);
        T item2 = elements.get(j);
        elements.set(i, item2);
        elements.set(j, item1);
        positionMap.put(item1, j);
        positionMap.put(item2, i);
    }
}

LeetCode 215: Kth Largest Element

public int findKthLargest(int[] nums, int k) {
    int heapSize = nums.length;
    for (int j = heapSize - 1; j >= 0; j--) {
        heapify(nums, j, heapSize);
    }
    
    for (int i = nums.length - 1; i >= nums.length - k + 1; i--) {
        swap(nums, 0, i);
        heapify(nums, 0, --heapSize);
    }
    return nums[0];
}

private void heapify(int[] data, int idx, int heapSize) {
    int left = 2 * idx + 1;
    while (left < heapSize) {
        int max = (left + 1 < heapSize && data[left + 1] > data[left]) 
            ? left + 1 : left;
        max = data[max] > data[idx] ? max : idx;
        if (max == idx) break;
        swap(data, idx, max);
        idx = max;
        left = 2 * idx + 1;
    }
}