数据结构:优先级队列(堆)
文章目录
1.优先级队列
1.1概念
队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列 ,在该场景中,队列显然不适用, 这时我们需要的操作是,一是返回最高优先级对象,二是添加新对象.这种数据结构称作优先级队列(Priority Queue)。
1.2优先级队列的模拟实现
在JDK1.8中的Priority Queue底层使用了堆这种数据结构 ，而堆实际就是在完全二叉树的基础上进行一些调整。
2.堆
2.1概念
如果有一个集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2(Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
2.2堆的存储方式
堆是一颗完全二叉树，可以利用层序遍历的规则采用顺序的方式来高效存储
对于非二叉树，则不适合使用顺序排序方式进行存储，会导致空间利用率比较低
将元素存储到数组中后，利用完全二叉树的性质对树进行还原，假设i为数组下标，有以下性质
- 当i=0时，则表示根节点，否则i节点的双亲节点为(i-1)/2
- 如果2*i+1小于节点个数，则节点i的左孩子为2*i+1,否则没有左孩子
- 如果2*i+2小于节点个数，则节点i的右孩子为2*i+2，否则没有右孩子
2.3堆的创建
2.3.1堆向下调整
对于集合{ 27,15,19,18,28,34,65,49,25,37 } 中的数据，首先利用层序遍历规则对树进行还原
此时树已经满足堆的性质了，只要进行向下调整即可
这里我们以大根堆为例:
1.parent记为需要调整的根节点，child记为parent根节点的左孩子
2.parent存在左孩子，即:child<size,进行下列操作，直到parent的左孩子不存在
- parent右孩子是否存在，存在找的左右孩子中较大的孩子，并将child修改为较大孩子的下标
- 将parent与较大的孩子child比较
- parent大于child,调整结束
- 否则，交换parent与child，交换结束后，parent中小的元素向下移动，可能导致树不能满足堆的结构，因此继续向下调整，即parent=child;child=parent*2+1;进行操作2.
private void shiftDown (int parent) { if (parent < 0) { return; } // 1. 先去找到左孩子节点 int child = parent * 2 + 1; while (child < size) { // 2. 判断有没有右孩子 if (child + 1 < size) { // 有右孩子节点，如右孩子节点的值比左孩子节点的值大，那么child就设置成右孩子节点的下标 if (elementData[child + 1] > elementData[child]) { child++; // 这时child下标对应的值是左右孩子节点中最大的那个 } } // 3. 用孩子节点中最大的值与父节点去比较 if (elementData[parent] >= elementData[child]) { break; } // 4. 交换父子节点的值 swap(elementData, parent, child); // 5. 向下调整，重置父子下标 parent = child; child = (parent * 2) + 1; } } private void swap(int[] elementData, int parent, int child) { int tmp=elementData[parent]; elementData[parent]=elementData[child]; elementData[child]=tmp; }
2.3.2堆的创建
核心为对集合进行向下调整
public Head(int []array) { //复制数组，防止array的修改影响elementData this.elementData = Arrays.copyOf(array, array.length); this.size = elementData.length; //向下调整为堆结构 int parent=(size-1-1)/2; for (int i = parent; i >=0 ; i--) { shiftDown(i); } }
2.4堆的插入与删除
2.4.1堆的插入
- 将元素放入到底层空间中(需判断是否需要扩容)
- 将最后插入的节点向上调整(与向下调整原理相似)，直到符合堆结构
public void offer(int val){ //判断数组是否满了 if (isFull()){ //2倍扩容 elementData=Arrays.copyOf(elementData,DEFAULT_CAPACITY*2); } //新元素插入到最后一个位置 elementData[size]=val; size++; shiftUp(size-1); } //向上调整 private void shiftUp(int child) { //判断是否越界 if (child>=size){ return; } int parent=(child-1)/2; //向上调整 while (child>0&&parent>=0){ //和父节点的值比较大小 if(elementData[child]<=elementData[parent]){ break; } //此时孩子节点的值比父节点的值大，交换 swap(elementData,parent,child); //重置父子下标 child=parent; parent=(child-1)/2; } } private boolean isFull() { return size==elementData.length; }
2.4.2 堆的删除
堆的删除实质是删除堆顶元素。
- 将堆顶元素与最后一个元素交换
- 将堆中有效数据个数减少一个
- 对堆顶元素进行向下调整
public int poll(){ //判断数组是否为空 if (isEmpty()){ throw new RuntimeException("数组为空"); } int val=elementData[0]; swap(elementData,0,size-1); size--; shiftDown(0); return val; } private boolean isEmpty() { return size==0; }
2.5用堆实现优先级队列
public class Head { //用一个数组存放数据 private int[] elementData; //数组元素个数 private int size; //数组大小 private int DEFAULT_CAPACITY=10; public Head() { this.elementData=new int [DEFAULT_CAPACITY]; this.size=0; } //通过一个数组创建堆 public Head(int []array) { //复制数组，防 止array的修改影响elementData this.elementData = Arrays.copyOf(array, array.length); this.size = elementData.length; //向下调整为堆结构 int parent=(size-1-1)/2; for (int i = parent; i >=0 ; i--) { shiftDown(i); } } // 向下调整的核心逻辑 private void shiftDown (int parent) { if (parent < 0) { return; } // 1. 先去找到左孩子节点 int child = parent * 2 + 1; while (child < size) { // 2. 判断有没有右孩子 if (child + 1 < size) { // 有右孩子节点，如右孩子节点的值比左孩子节点的值大，那么child就设置成右孩子节点的下标 if (elementData[child + 1] > elementData[child]) { child++; // 这时child下标对应的值是左右孩子节点中最大的那个 } } // 3. 用孩子节点中最大的值与父节点去比较 if (elementData[parent] >= elementData[child]) { break; } // 4. 交换父子节点的值 swap(elementData, parent, child); // 5. 向下调整，重置父子下标 parent = child; child = (parent * 2) + 1; } } private void swap(int[] elementData, int parent, int child) { int tmp=elementData[parent]; elementData[parent]=elementData[child]; elementData[child]=tmp; } /** * 堆的插入 * @param val */ public void offer(int val){ //判断数组是否满了 if (isFull()){ //2倍扩容 elementData=Arrays.copyOf(elementData,DEFAULT_CAPACITY*2); } //新元素插入到最后一个位置 elementData[size]=val; size++; shiftUp(size-1); } //向上调整 private void shiftUp(int child) { //判断是否越界 if (child>=size){ return; } int parent=(child-1)/2; //向上调整 while (child>0&&parent>=0){ //和父节点的值比较大小 if(elementData[child]<=elementData[parent]){ break; } //此时孩子节点的值比父节点的值大，交换 swap(elementData,parent,child); //重置父子下标 child=parent; parent=(child-1)/2; } } private boolean isFull() { return size==elementData.length; } /** * 堆的删除 * @return */ public int poll(){ //判断数组是否为空 if (isEmpty()){ throw new RuntimeException("数组为空"); } int val=elementData[0]; swap(elementData,0,size-1); size--; shiftDown(0); return val; } private boolean isEmpty() { return size==0; } public int peek(){ return elementData[0]; } public void display(){ StringBuilder sb=new StringBuilder(); sb.append("["); for (int i = 0; i < size; i++) { sb.append(elementData[i]); if (i<size-1){ sb.append(","); } } sb.append("]"); sb.toString(); System.out.println(sb); } }
3.PriorityQueue
Java集合框架为我们提供了2种优先级队列的接口:PriorityQueuePriorityBlockingQueue,PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的 。
3.1注意
- 使用PriorityQueue是必须导入相应的包
import java.util.PriorityQueue;
- PriorityQueue中放置的元素必须能够比较大小，否则抛出ClassCastException异常
- 插入对象不能为null，否则抛出NullPointerException异常
- 内部默认容量为11，空间不足时会进行扩容
- 默认情况下是小根堆，如需要大根堆需要用户提供比较器
3.2常用的接口
构造方式
插入/删除/获取优先级最高的元素
olean offer(E e) | 插入元素e，插入成功返回true，如果e为空，抛出NullPointerException异常，空间不足时会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
