堆
堆的概念
- 堆是一颗顺序存储的二叉树,激素hi将二叉树层序遍历放到数组当中,是完全二叉树。
- 已知双亲(parent)的下标,则: 左孩子(left)下标 = 2 * parent + 1。 右孩子(right)下标 = 2 * parent + 2。
- 已知孩子(不区分左右)(child)下标,则: 双亲(parent)下标 = (child - 1) / 2。
- 堆有大根堆和小根堆两种: 大根堆:每个根都比结点大。 小根堆:每个根都比结点小。
- 堆对应的集合:priorityQueue(优先级队列)是完全二叉树。
- 堆物理上是保存在数组当中
实现堆
因为堆在物理上是数组,所以通过数组来实现。
定义参数
publicint[] elem;publicint usedSize;publicTestHeap(){this.elem =newint[10];}
向下调整
把数据从上往下调整,然后形成堆。但前提是:左右子树必须已经是一个堆,才可以调整。一般在插入元素的时候进行向下调整。
说明
- array 代表存储堆的数组
- size 代表数组中被视为堆数据的个数
- index 代表要调整位置的下标
- left 代表 index 左孩子下标
- right 代表 index 右孩子下标
- min 代表 index 的最小值孩子的下标
过程
- index 如果已经是叶子结点,则整个调整过程结束: 判断 index 位置有没有孩子 因为堆是完全二叉树,没有左孩子就一定没有右孩子,所以判断是否有左孩子 因为堆的存储结构是数组,所以判断是否有左孩子即判断左孩子下标是否越界,即 left >= size 越界
- 确定 left 或 right,谁是 index 的最小孩子 min 如果右孩子不存在,则 min = left 否则,比较 array[left] 和 array[right] 值得大小,选择小的为 min
- 比较 array[index] 的值 和 array[min] 的值,如果 array[index] <= array[min],则满足堆的性质,调整结束
- 否则,交换 array[index] 和 array[min] 的值
- 然后因为 min 位置的堆的性质可能被破坏,所以把 min 视作 index,向下重复以上过程
如图
像这样通过向下调整,就得到了一个小根堆。
调整前:int[] array = { 27,15,19,18,28,34,65,49,25,37 };
调整后:int[] array = { 15,18,19,25,28,34,65,49,27,37 };
所以代码如下:
publicvoidshiftDown(int parent,int len){int child =2*parent+1;while(child < len){if(child +1< len && elem[child]< elem[child +1]){
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;}}}
创建堆
因为向下调整是适用于插入一个数据之后依然是堆,所以我们可以从第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。代码如下:
publicvoidcreateHeap(int[] array){for(int i =0; i < array.length; i++){
elem[i]= array[i];this.usedSize++;}for(int parent =(usedSize-1-1)/2; parent >=0; parent--){//调整shiftDown(parent, usedSize);}}
向上调整
向上调整用在入堆的时候。当一个元素入堆之后,其实是放在二叉树的最后面的。如图:
把新入堆的元素调整之后,保证还是一个大根堆或者小根堆。代码如下:
privatevoidshiftUp(int child){int parent =(child -1)/2;while(parent >=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;}}}
判断是否满
判断是否满的时候,只需将 usedSize 和数组长度比较就可以了。代码如下:
publicbooleanisFull(){return usedSize == elem.length;}
插入堆
向上调整是为了方便一个元素插入堆中,所以插入的时候,只需判断是否满了,如果没满,就向上调整。代码如下:
publicvoidoffer(int val){if(isFull()){//满了 扩容
elem =Arrays.copyOf(elem,2*elem.length);}
elem[usedSize++]= val;//传入的是 usedSize - 1shiftUp(usedSize-1);}
判断堆是否为空
判空的方法就是看 usedSize 是否为 0 即可。
publicbooleanisEmpty(){return usedSize ==0;}
出堆顶元素
先判断堆是否为空,然后拿到堆顶元素,然后把堆顶元素的值改为堆的最后一个元素,然后向下调整就好了。代码如下:
publicintpoll(){if(isEmpty()){thrownewRuntimeException("优先级队列为空!");}int tmp = elem[0];
elem[0]= elem[usedSize -1];
elem[usedSize -1]= tmp;
usedSize--;shiftDown(0,usedSize);return tmp;}
拿到堆顶元素
先判断堆是否为空,然后返回数组 0 下标的元素就可以了。代码如下:
publicintpeek(){if(isEmpty()){thrownewRuntimeException("优先级队列为空!");}return elem[0];}
堆排序
这里的排序就是每次都进行向下调整,直到全部调整完成。代码如下:
publicvoidheapSort(){int end =this.usedSize-1;while(end >0){int tmp = elem[0];
elem[0]= elem[end];
elem[end]= tmp;shiftDown(0,end);
end--;}}
代码测试
publicstaticvoidmain(String[] args){int[] arr ={27,15,19,18,28,34,65,49,25,37};TestHeap testHeap =newTestHeap();
testHeap.createHeap(arr);//得到调整之后的结果System.out.println(Arrays.toString(testHeap.elem));
testHeap.offer(80);//每次入队之后还是大根堆System.out.println(Arrays.toString(testHeap.elem));//每次出队 也要保证大根堆和小根堆 先交换 0 下标和最后下标的位置,然后向下调整就可以了System.out.println(testHeap.poll());//每次弹出的都是最大的元素System.out.println(Arrays.toString(testHeap.elem));}
运行结果如下:
测试堆排序
publicstaticvoidmain(String[] args){int[] arr ={27,15,19,18,28,34,65,49,25,37};TestHeap testHeap =newTestHeap();
testHeap.createHeap(arr);
testHeap.heapSort();System.out.println(Arrays.toString(testHeap.elem));}
运行结果如下:
优先级队列
优先级队列是 : PriorityQueue 。这里默认就是一个小根堆,每次放入之后还是小根堆。弹出之后还是小根堆。代码如下:
publicstaticvoidmain2(String[] args){PriorityQueue<Integer> priorityQueue =newPriorityQueue<>();
priorityQueue.offer(12);
priorityQueue.offer(3);
priorityQueue.offer(15);System.out.println(priorityQueue.poll());System.out.println(priorityQueue.poll());}
运行结果如下:
版权归原作者 Lockey-s 所有, 如有侵权,请联系我们删除。