Heap sort

1.Heap sort

• Uses a heap to help sort elements in ascending or descending order

steps

• phase 1. Heapify: First converts the unsorted list or array into a heap - This can be done in place

  • Keep adding additional elements into the heap portion ensuring that these additional elements also satisfy the heap property

  • The heap will grow to encompass all elements in the array

    //從最後一個node的parent開始percolateDown
    //往前移動
    
    public static void heapify(int endIndex) {
        int index = getParentIndex(endIndex);
        while (index > 0) {
            percolateDown(index, endIndex);
            index--;
        }
    }
    
    private static void percolateDown(int index, int endIndex) {
        int leftChildIndex = getLeftChild(index, endIndex);
        int rightChildIndex = getRightChild(index, endIndex);
        
        //一但左子存在, 且左子比較大, 則swap並且繼續percolateDown
        if (leftChildIndex != -1 && array[leftChildIndex] > array[index]) {
            swap(leftChildIndex, index);
            percolateDown(leftChildIndex, index);
        }
        
        if (rightChildIndex != -1 && array[rightChildIndex] > array[index]) {
            swap(rightChildIndex, index);
            percolateDown(rightChildIndex, index);
        }
    }
    
    public int getLeftChild(int index, int endIndex) {
        int leftChildIndex = 2 * index + 1;
        if (leftChildIndex >= endIndex) {
            return -1;
        }
    
        return leftChildIndex;
    }
    
    public int getRightChild(int index, int endIndex) {
        int rightChildIndex = 2 * index + 2;
        if (rightChildIndex >= endIndex) {
            return -1;
        }
    
        return rightChildIndex;
    }
    
    public int getParentIndex(int index) {
        if (ijndex < 0 || index > count) {
            return -1;
        }
    
        return (index - 1)/2;
    }
    
    protected void swap(int index1, int index2) {
        T tempValue = array[index1];
        array[index1] = array[index2];
        array[index1] = tempValue;
    }

• 2.Use the heap to access the maximum element and put it in the right position in the array (sort)

  • A heap offer O(1) access to the largest of the smallest element

    public static void heapsort() {
        heapify(array.length - 1);
        int endIndex = array.length - 1;
        while (endIndex > 0) {
            swap(0, endIndex);
            endIndex--;
            percolateDown(0, endIndex);
        }
    }

2.Complexity

• Insert: O(log n)

• Remove: O(log n)

• Average: O(n log n)

• not adaptive

• not stable

• space: O(1)