# 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**&#x20;
  * 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&#x20;

```
    //從最後一個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&#x20;

```
    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)
