一 堆
分为大根堆和小根堆
child=2*parent+1
parent=(child-1)/2
创建大根堆
public int[]elem; public int usedsize; public TestHeap(){ int[] elem=new int[10]; } public void heapCreat(int[] arr){ for (int i = 0; i < arr.length; i++) { elem[i] = arr[i]; usedsize++; } int parent=((usedsize-1)-1)/2; for (; parent >=0 ; parent--) { shiftDown(usedsize,parent); } }
向下调整(为了使每个根成为最大,调整后使parent=child查看是否有没有调整的)
public void shiftDown( int len,int parent){ int child=2*parent+1; while (child<len){ if (elem[child]<elem[child+1] && child+1<len){ child++; //保证左右孩子的最大值下标 } if (elem[child]>elem[parent]){ int tmp=elem[child]; elem[child]=elem[parent]; elem[parent]=tmp; parent=child; child=2*parent+1; }else { break; } } }
向上调整(将一个元素先放到usedsize-1的位置然后开始比较,如果大了就换)
public void offer(int val){ if (isFull()){ elem= Arrays.copyOf(elem,2*elem.length); } elem[usedsize++]=val; shiftUp(usedsize-1); //注意这里的传参容易出错 } public void shiftUp(int child) { int parent=(child-1)/2; while (child>0){ if (elem[child]>elem[parent]){ int tmp=elem[child]; elem[child]=elem[parent]; elem[parent]=tmp; child=parent; parent=(child-1)/2; }else { break; } } }
public boolean isFull(){
return usedsize==elem.length;
}
出队(出队使0下标的位置和最后一个位置进行交换,然后usedsize要--)
public int poll(){ if (ifempty()){ throw new RuntimeException("优先为空"); } int tmp=elem[0]; elem[0]=elem[usedsize-1]; elem[usedsize-1]=tmp; usedsize--; shiftDown(usedsize,0); return tmp; }
返回队首元素(直接返回数组0下标)
public boolean ifempty(){ return usedsize==0; } //返回队首元素 public int peek(){ if (ifempty()){ throw new RuntimeException("优先为空"); } return elem[0]; }
标签:parent,int,使用,usedsize,elem,child,public From: https://www.cnblogs.com/lbwboke/p/16664477.html