[数据结构与算法]算法学习：堆排序

一、堆概念

堆结构就是用数组形成的完全二叉树结构。
完全二叉树如果每一个子树父节点都为最大值则成为大根堆
完全二叉树如果每一个子树父节点都为最小值则成为小根堆

完全二叉树 ： 从左到右依次插入则为完全二叉树

• 堆的几个基本公式
  • 左子树下标 2*i+1
  • 右子树下标 2*i+2
  • 父节点 i-1/2

大根堆 ：已头为首每颗子树最大值都是头节点 父节点大于子节点

堆算法 heapIndex

用于将数字形成完全二叉树 从下往上一次比较

1，3，4，2，8，4 每一位与父节点pk大则交换
如3与 i-1/2比较

  public static void headIndex(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            arr[index] = arr[index] ^ arr[(index - 1) / 2];
            arr[(index - 1) / 2] = arr[index] ^ arr[(index - 1) / 2];
            arr[index] = arr[index] ^ arr[(index - 1) / 2];
            index = (index - 1) / 2;
        }
    }

堆算法 heapify

从上往下一次进行堆比较

  public static void heapify(int[] arr, int index, int heapsize) {
        int left = index * 2 + 1; //获取左节点
        while (left < heapsize) { //判断左节点与数字大小是否越界
        	//左节点与右节点比较大小 取下标
            int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
            //当前位置与自己左右子树比较大小
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            //交换
            arr[largest] = arr[largest] ^ arr[index];
            arr[index] = arr[largest] ^ arr[index];
            arr[largest] = arr[largest] ^ arr[index];
            //游标转移
            index = largest;
            //游标转移
            left = index * 2 + 1;
        }
    }

堆排序

步骤：

1. 先将给定数组通过heapIndex or heapify 转换为完全二叉树大根堆
2. 转换完成后 index=0的位置已经确保最大 头尾替换 index 0 与 size 交换
3. 头部开始进行heapify操作再次形成大根堆 以此类推

   public static void headIndex(int[] arr, int index) {

        while (arr[index] > arr[(index - 1) / 2]) {
            arr[index] = arr[index] ^ arr[(index - 1) / 2];
            arr[(index - 1) / 2] = arr[index] ^ arr[(index - 1) / 2];
            arr[index] = arr[index] ^ arr[(index - 1) / 2];
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapsize) {
        int left = index * 2 + 1;
        while (left < heapsize) {
            int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            arr[largest] = arr[largest] ^ arr[index];
            arr[index] = arr[largest] ^ arr[index];
            arr[largest] = arr[largest] ^ arr[index];
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 3, 4, 8, 11, 7, 2, 13};
        for (int i = 0; i < arr.length; i++) {
            headIndex(arr, i);
        }

        int heapSize = arr.length;
        swap(arr,0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr,0, --heapSize);
        }
        for (int i : arr) {
            System.out.println(i);
        }

    }