堆排序算法（HeapSort）

1.堆（heap）

（1）堆的概念
若n个关键字序列$L[\mathrm{1...}n]$满足下面某一条性质，则称为堆（heap）：
1）大根堆：$L(i)>=L(2i)$且$L(i)>=L(2i+1)$ $(1<=i<=n/2)$
2）小根堆：$L(i)<=L(2i)$且$L(i)<=L(2i+1)$ $(1<=i<=n/2)$
说明：可理解为顺序存储的完全二叉树，其每个结点的值大于其左右孩子结点的值

（2）堆的插入
先将新元素放到表尾，与父结点对比，若新元素比父结点更大（小）则将二者互换，若元素互换破坏了上一层级的堆性质，则采用相同的方法继续上调，直到无法上调为止

（3）堆的删除
用表尾的元素代替被删除的元素，若破坏了堆的性质，则与孩子结点中更大（小）的结点互换，若元素互换破坏了下一层级的堆性质，则采用相同的方法继续下调，直到无法下调为止

2.堆排序算法（HeapSort）

（1）堆排序算法思想
每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素再次调整为大（小）根堆

（2）适用范围
顺序表

2.建立大（小）根堆

把所有非终端结点都检查一遍，是否满足大（小）根堆的要求，如果不满足，则将当前结点与更大（小）的孩子互换，若元素互换破坏了下一层级的堆性质，则采用相同的方法继续向下调整

3.堆排序算法性能分析

4.堆排序算法代码实现（Java）

public void heapSort(int[] arr, int len){
        buildMaxHeap(arr, len);
        for(int i = len ; i > 1 ; i--){
            int temp = arr[1];
            arr[1] = arr[i];
            arr[i] = temp;
            adjustHead(arr, 1, i-1);
        }
}

public void buildMaxHeap(int[] arr, int len){
        for(int i = (len - 1) / 2 ; i >= 0 ; i--){
            adjustHead(arr, i , len);
        }
}

public void adjustHead(int[] arr, int k, int len){
        arr[0] = arr[k];
        for(int j = 2 * k ; j <= len ; j *= 2){
            if(j < len && arr[j] < arr[j+1]){
                j++;
            }
            if(arr[0] > arr[j]){
                break;
            }else{
                arr[k] = arr[j];
                k = j;
            }
        }
        arr[k] = arr[0];
}