大顶堆的基本操作

目录

堆的基本操作

//堆排序

---

堆的基本操作

​​​​​
* 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);}
}