堆排序

堆排序

完全二叉树

设二叉树的深度为h，除第 h 层外，其它各层 （1～h-1）的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边

如将一棵有n个结点的完全二叉树自顶向下，同层自左向右连续为结点编号0,1, …, n-1，则有：

1. 若i = 0, 则 i 无双亲, 若i > 0, 则 i 的双亲为」(i -1)/2」

2. 若2*i+1 < n, 则i 的左孩子为 2*i+1，若2*i+2 < n, 则 i 的右孩子为2*i+2

3. 若结点编号i为偶数，且i != 0,则左兄弟结点 i-1.

4. 若结点编号i为奇数，且i != n-1,则右兄弟结点为 i+1.

5. 结点 i 所在层次为」log2(i+1) 」

6. 在二叉树上的第 i 层上至多有2^(i-1)个节点（i>=1）

7. 深度为 k 的二叉树至多有(2^k)-1个节点（k>=1）

8. 具有n个节点的完全二叉树的深度为 」log2n」+ 1

性质8证明：

假设两种极端情况

1. 该树为满二叉树时，结点n1=2^k-1，此时k=log2（n1+1）

2. 当该树为满二叉树附加一个结点时，结点n2=2^（k-1）,此时k=log2（n2） +1,并且log2（n1+1）= log2（n2） +1

对任意结点n的完全二叉树，n2<=n<=n1

2^（k-1）<= n <= 2^k -1

log2（n+1） <= k <= log2n +1

则 k = 」log2n」+ 1

第一个非叶子节点怎么找？

其实就是算最后一个节点的父节点的下标，最后一个节点的下标为数组长度 - 1，根据完全二叉树的性质1可得其父节点为（length - 1 - 1）/ 2

代码

import java.util.Arrays;

public class heapSort {
    public static void main(String[] args) {
        int[] nums = new int[]{4,345,46,56,65,563,342,1,2,4};
        heapsort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private static void heapsort(int[] nums) {
        //构造初始堆，从第一个非叶子节点开始调整
        for(int k = (nums.length - 2) >> 1; k >= 0; k--){
            headAdjust(nums,nums.length,k);
        }
        //构造大顶堆，从末尾开始依次跟根节点交换并重新调整，这样就可以从小到大排序
        for(int i = nums.length - 1; i > 0; i--){
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            headAdjust(nums,i,0);
        }
    }

    private static void headAdjust(int[] nums, int length, int k) {
        int temp = nums[k];
        //左孩子
        int i = 2 * k + 1;
        //不断向下调整
        while(i < length){
            if(i + 1 < length){
                if(nums[i] < nums[i + 1])i++;
            }
            //构造大顶堆，大于nums[k]继续比较，否则退出循环
            if(nums[i] > temp){
                nums[k] = nums[i];
                k = i;
                i = 2 * k + 1;
            }else break;
        }
        nums[k] = temp;
    }
}