学做川菜下什么网站,品牌广告图片,wordpress 时间轴页面,做公众号的网站模板堆 在Java中有一种数据结构基于队列#xff0c;并保证操作的数据带有优先级#xff0c;该数据结构应该提供了两个最基本的操作#xff0c;一个是返回最高优先级对象#xff0c;一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。它的底层使用了堆这种数据结…堆 在Java中有一种数据结构基于队列并保证操作的数据带有优先级该数据结构应该提供了两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。它的底层使用了堆这种数据结构堆其实就是在二叉树的基础上进行了一些调整。 1.什么是堆
堆的概念 堆能把它的所有元素按照完全二叉树的方式存储在一个一维数组中并保证每次出队列的元素都是这些元素中的最大值或最小值。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一颗完全二叉树 完全二叉树 一般二叉树 堆的存储方式 前面过二叉树的存储方式有两种数组或链表因为数组存储的方式在二叉树不是完全二叉树的情况下有明显的对内存的浪费所以我们当时选择了链表的方式但是堆肯定是一颗完全二叉树在这里我们利用层序的规则采用数组来高效存储。
如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2如果2 * i 1 小于节点个数则节点i的左孩子下标为2 * i 1否则没有左孩子如果2 * i 2 小于节点个数则节点i的右孩子下标为2 * i 2否则没有右孩子
2.优先级队列堆的实现
我们以创建一个小根堆为例如何创建一个小根堆呢 其实这是一个不断向下调整的过程定义parent等于二叉树的根节点同过让它不断与孩子节点进行比较和交换位置将这样的过程重复就能得到一个堆了具体过程如下
1. 让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子) 2. 如果parent的左孩子存在即:child size 进行以下操作直到parent的左孩子不存在
parent右孩子是否存在存在找到左右孩子中最小的孩子让child进行标记将parent与较小的孩子child比较如果
parent小于较小的孩子child调整结束否则交换parent与较小的孩子child交换完成之后parent中大的元素向下移动可能导致子树不满足对的性质因此需要继续向下调整即parent childchild parent*21; 然后继续2。 堆的插入
堆的插入总共需要两个步骤 1. 先将元素放入到底层空间中(注意空间不够时需要扩容) 2. 将最后新插入的节点向上调整直到满足堆的性质 堆的删除 堆的删除一定删除的是堆顶元素。我们可以通过以下步骤进行删除操作
1. 将堆顶元素对堆中最后一个元素交换 2. 将堆中有效数据个数减少一个 3. 对堆顶元素进行向下调整
由上述可知创建一个自己的堆重点需要手写向上调整和向下调整的方法解决了这两个方法堆的操作便可迎刃而解了。下面的优先级队列的代码实现
public class MyPriorityQyueue {public int[] array;public int usedSize;public MyPriorityQyueue(){this.arraynew int[10];}public void initArray(int[] arr){for(int i0;iarr.length;i){array[i]arr[i];usedSize;}}public void createHeap() {for (int parent (usedSize-1-1)/2; parent 0 ; parent--) {shiftDown(parent,usedSize);}}public void offer(int val) {if(isFull()) {//扩容array Arrays.copyOf(array,2*array.length);}array[usedSize] val;//11//向上调整shiftUp(usedSize-1);//10}public int pop() {if(isEmpty()) {return -1;}int retarray[0];swap(array,0,usedSize-1);usedSize--;shiftDown(0,usedSize);return ret;}public int peek(){if(isEmpty()) {return -1;}return array[0];}public boolean isEmpty() {return usedSize 0;}private void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;}public boolean isFull() {return usedSize array.length;}private void shiftDown(int parent,int len){int child 2*parent1;while(childlen){if(child1lenarray[child]array[child1]){child;}if(array[child]array[parent]){int tmparray[child];array[child]array[parent];array[parent]tmp;parentchild;child2*parent1;}else{break;}}}private void shiftUp(int child) {int parent (child-1)/2;while (child 0) {if(array[child] array[parent]) {int tmp array[child];array [child] array[parent];array[parent] tmp;child parent;parent (child-1)/2;}else {break;}}}
} 3.PriorityQueue的使用 PriorityQueue是Java对堆的一个实现类继承了Queue接口。
PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出ClassCastException异常不能插入null对象否则会抛出NullPointerException没有容量限制可以插入任意多个元素其内部可以自动扩容插入和删除元素的时间复杂度为O(log2N)PriorityQueue底层使用了堆数据结构PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
在Java中重写comparator方法可实现小根堆到大根堆的转换
Anew PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}
});常用方法
函数名功能介绍boolean offer(E e)插入元素e插入成功返回truee不能为空会自动扩容。时间复杂度Olog2N。E peek()获取优先级最高的元素。E poll()移除优先级最高的元素并返回。int size()获取有效元素的个数void clear()清空boolean isEmpty()检测优先级队列是否为空。
优先级队列的扩容说明 如果容量小于64时是按照oldCapacity的2倍方式扩容的 如果容量大于等于64是按照oldCapacity的1.5倍方式扩容的 如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容
4.优先级队列的应用
利用堆排序的思想解决TOP-K问题
在数据量极大的情况下求数据集合中前K个最大的元素或者最小的元素。 因为此时数据太大无法一次性全部加载到内存中不能使用一般的排序方法来进行求解了最佳方式用堆求解思路如下
1.用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆
2.用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
