堆&&堆排序相关

//插入逐步实现大根堆
    public static void heapInsert(int[] arr, int curr) {
        while (arr[curr]>arr[parent(curr)]){
            swap(arr,curr,parent(curr));
            curr=parent(curr);
        }
    }
这里我们每步都假设前面数据已经实现大根堆,所以是将curr当前索引上数据与前面数据比较继续大根堆

如果我们想实现一个数组堆化,只要保证后续每插入一个都保持堆化就好
eg:
  //堆化数组
        for(int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }

   //堆的大小为size即数组0~size-1
    //维持index结点所在子树为大根堆 (父结点大)
    //如果index位置变化也可以用此函数维持大根堆
    //size为数组长度,而不是最后一个索引,是最后一个堆位置索引值+1
    public static void heapify(int[] arr, int index, int size) {
        while (left(index)<size){
            //当存在左孩子节点
            //判断两个子结点的值大小,得到最大值的索引
            //如果存在右节点且大于左结点,返回右节点值
            //否则返回左节点值
            int largest=right(index)<size&&arr[right(index)]>arr[left(index)]
                    ?right(index)
                    :left(index);
            //将孩子中大值和index父结点比较,得到最大值索引从而交换让父结点得到最大值
            largest=arr[largest]>arr[index]?largest:index;
            if (largest == index) {
                break;
            }
            swap(arr,index,largest);
            index=largest;

        }
    }

package com.day1.sort;

import com.day1.comparator.ArrayComparator;

public class HeapSort extends ArrayComparator {
    public static void main(String[] args){  
        int [] iarr={5,4,1,2,8,6};
       heapSort(iarr);
        printArray(iarr);
    }
    //堆排序
    public static void heapSort(int[] arr) {
        if (arr==null||arr.length<2) { //如果数组为空或者长度为小于等于1
            return;
        }
        //堆化数组
        for(int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }
        int heapsize=arr.length;//堆在数组里的长度
        while (heapsize!=0){
            swap(arr,0,--heapsize);//将头结点和尾结点交换,把最大值放最后
            heapify(arr,0,heapsize);//保持树化
        }
    }

    //插入逐步实现大根堆
    public static void heapInsert(int[] arr, int curr) {
        while (arr[curr]>arr[parent(curr)]){
            swap(arr,curr,parent(curr));
            curr=parent(curr);
        }
    }


    //堆的大小为size即数组0~size-1
    //维持index结点所在子树为大根堆 (父结点大)
    //如果index位置变化也可以用此函数维持大根堆
    //size为数组长度,而不是最后一个索引,是最后一个堆位置索引值+1
    public static void heapify(int[] arr, int index, int size) {
        while (left(index)<size){
            //当存在左孩子节点
            //判断两个子结点的值大小,得到最大值的索引
            //如果存在右节点且大于左结点,返回右节点值
            //否则返回左节点值
            int largest=right(index)<size&&arr[right(index)]>arr[left(index)]
                    ?right(index)
                    :left(index);
            //将孩子中大值和index父结点比较,得到最大值索引从而交换让父结点得到最大值
            largest=arr[largest]>arr[index]?largest:index;
            if (largest == index) {
                break;
            }
            swap(arr,index,largest);
            index=largest;

        }
    }
    //求父结点
    public static int parent(int i) {
        return (i-1)/2;
    }


    //求左孩子
    public static int left(int i) {
        return 2*i+1;
    }
    //求右孩子
    public static int right(int i) {
        return 2*i+2;
    }
    //交换
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}