大顶堆的基本操作

目录

堆的基本操作

//堆排序

堆的基本操作

​​​​​
* 1.找到最后一个非叶子节点
* 2.从后向前遍历，对每个节点执行下潜操作

删除堆顶元素
* 1.将堆顶元素与最后一个元素交换位置
* 2.将最后一个元素删除
* 3.然后从上向下调整堆
 

public class MaxHeap {
    int [] array;
    int size;
    public MaxHeap(int capacity)
    {
        array=new int[capacity];
    }
    public MaxHeap(int []array){
        this.array=array;
        size=array.length;
        heapify();
    }
    //建堆  把数组调整为大顶堆的形式
    private void heapify(){
        //找到最后一个非叶子节点  size/2-1 (size是从零开始计数)
        for(int i=size/2-1;i>=0;i--){
            down(i);
        }
    }
    //parent是下潜的元素,与两个子节点比较，如果比子节点大，则交换，然后继续下潜
        private void down(int parent) {
        int left=2*parent+1;
        int right=2*parent+2;
        int max=parent;
        if(left<size&&array[left]>array[max]){//left<size 是为了防止越界,在索引有意义的范围内进行比较
            max=left;
        }
        if(right<size&&array[right]>array[max]){
            max=right;
        }
        if(max!=parent){
            swap(max,parent);
            down(max);
        }

    }
//交换位置
    private void swap(int i, int j) {
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    //获取堆顶元素
    public int peek(){
        if(size==0){
            return Integer.MIN_VALUE;
        }
        return array[0];
    }
    //删除堆顶元素
    public int poll(){
        if(size==0){
            return Integer.MIN_VALUE;
        }
        int result=array[0];
        swap(0,--size);
        down(0);
        array[size]=0;
        return result;
    }
    //删除指定元素
    public int poll(int index){
        int delete=array[index];
        swap(index,--size);
        down(index);
        array[size]=0;
        return delete;
    }
    //替换堆顶元素
    public void replace(int value){
        array[0]=value;
        down(0);
    }
    //堆的尾部添加元素
   public boolean offer(int value){
        if(size==array.length){
            return false;
        }
        up(value);
        size++;
        return true;
   }

    private void up(int value) {
        int child = size;
        while(child>0){
            int parent=(child-1)/2;
            if(array[parent]<value){
                array[child]=array[parent];
                child=parent;
            }else{
                break;
            }
        }
        array[child]=value;  //进入不了循环的在这进行插入
    }
}

//堆排序

/*
* 1.heapify()建立大顶堆
* 2.将堆顶与堆底的元素交换位置，缩小并下潜调整堆
* 3.重复2，3直到堆剩一个元素
* */

public class MaxHeapDemo1 {
    int [] array;
    int size;
    public MaxHeapDemo1(int capacity)
    {
        array=new int[capacity];
    }
    public MaxHeapDemo1(int []array){
        this.array=array;
        size=array.length;
        heapify();
    }
    //建堆
    private void heapify(){
        for(int i=size/2-1;i>=0;i--){
            down(i);
        }

    }
    //下潜
    private void down(int parent){
        int left=2*parent+1;
        int right=2*parent+2;
        int max=parent;
        if(left<size&&array[left]>array[max]){
            max=left;
        }
        if(right<size&&array[right]>array[max]){
            max=right;
        }
        if(max!=parent){
            swap(max,parent);
            down(max);
        }

    }
    //交换
    private void swap(int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;

    }
    public String toString(){
        return Arrays.toString(array);
    }
}