堆排序

完全二叉树:
上面的层级是满的 最后一层 依次填过来
i节点左右儿子的下标
2i+1;
2i+2;
(i-1)/2 找父节点
大根堆: 每个头节点 都是子树的最大值
小根堆: 每个头节点 都是子树的最小值
heapsize: 表示堆的大小
用数组来脑补树的结构
建大堆过程

• 来一个树 heapsize ++;
• ---->父节点 往上走 循环 是logn 级别的 (树的高度)

heap insert
static void heapinsert(int a[] ,int index ){
    while(a[index]>a[(index-1)/2]){//照顾了==0 也不进去循环
      swap(a,index ,(index-1)/2);
      index=(index-1)/2;
  }
}

拿走最大值 然后 再调整成一个大根堆

• 把最后一个数字去填 堆顶
• 然后 heapsize --
• 堆顶<左或右孩子 把左右孩子中大的那个和堆顶交换

heapify
static void heapify(int a[] ,int index,int heapsize ){
 int left =index*2+1;
while(left <heapsize){
找左右孩子中最大的那个的下标
int largest=left+1<heapsize&&a[left+1]>a[left]?left+1:left;
找左右 index 中的下标
largest=a[index]>a[left]?index:left;
if(largest==index){//找到了最大  刚刚忘了!
break;}
swap(a,index,largest);//刚忘了!
index=largest;
left=index*2+1;
}
}
也是logn

堆排序:

• 建堆
  insert

循环

• 拿堆顶 拿最后一个数换堆顶
• heapify
  heapsize--

如果是直接给你了一个数组 建堆过程可以优化成 自底向下 每个数都去 heapify
证明是O(n)

堆排的过程
   static void heapsort(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }
        for (int i = 0; i < a.length; i++) { //建堆
            heapinsert(a, i);
        }
        int size = a.length;
        swap(a, 0, --size);
        while (size > 0) {//开始循环去把一个个数换到后面去
            heapify(a, 0, size);
            swap(a, 0, --size);
        }
    }

    //    heapify
    static void heapify(int a[], int index, int heapsize) {
        int left = index * 2 + 1;
        while (left < heapsize) {
//            找左右孩子中最大的那个的下标
//            int largest = left + 1 <=heapsize && a[left + 1] > a[left] ? left + 1 : left;
            int largest = left + 1 < heapsize && a[left + 1] > a[left] ? left + 1 : left; //left 是下标 size 是数量== 情况不成立
//            找左右 index 中的下标
            largest = a[index] > a[largest] ? index : largest;//坑!largest 写成了 left
            if (largest == index) {//找到了最大  刚刚忘了!
                break;
            }
            swap(a, index, largest);//刚忘了!
            index = largest;
            left = index * 2 + 1;
        }
    }

    static void heapinsert(int a[], int index) {
        while (a[index] > a[(index - 1) / 2]) {//照顾了==0 也不进去循环
            swap(a, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    static void swap(int[] a, int i, int j) {
        int tem = a[i];
        a[i] = a[j];
        a[j] = tem;
    }