在Java中有一种数据结构基于队列,并保证操作的数据带有优先级,该数据结构应该提供了两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。它的底层使用了堆这种数据结构,堆其实就是在二叉树的基础上进行了一些调整。
堆的概念:
堆能把它的所有元素按照完全二叉树的方式存储在一个一维数组中,并保证每次出队列的元素都是这些元素中的最大值或最小值。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
完全二叉树
一般二叉树
堆的存储方式:
前面过二叉树的存储方式有两种,数组或链表,因为数组存储的方式在二叉树不是完全二叉树的情况下,有明显的对内存的浪费,所以我们当时选择了链表的方式,但是堆肯定是一颗完全二叉树,在这里我们利用层序的规则采用数组来高效存储。
我们以创建一个小根堆为例,如何创建一个小根堆呢?
其实这是一个不断向下调整的过程,定义parent等于二叉树的根节点,同过让它不断与孩子节点进行比较和交换位置,将这样的过程重复就能得到一个堆了,具体过程如下:
1. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在
堆的插入:
堆的插入总共需要两个步骤: 1. 先将元素放入到底层空间中(注意:空间不够时需要扩容) 2. 将最后新插入的节点向上调整,直到满足堆的性质
堆的删除:
堆的删除一定删除的是堆顶元素。我们可以通过以下步骤进行删除操作:
1. 将堆顶元素对堆中最后一个元素交换 2. 将堆中有效数据个数减少一个 3. 对堆顶元素进行向下调整
由上述可知,创建一个自己的堆重点需要手写向上调整,和向下调整的方法,解决了这两个方法,堆的操作便可迎刃而解了。下面的优先级队列的代码实现:
public class MyPriorityQyueue {
public int[] array;
public int usedSize;
public MyPriorityQyueue(){
this.array=new int[10];
}
public void initArray(int[] arr){
for(int i=0;i<arr.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 ret=array[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*parent+1;
while(child<len){
if(child+1<len&&array[child]<array[child+1]){
child++;
}
if(array[child]<array[parent]){
int tmp=array[child];
array[child]=array[parent];
array[parent]=tmp;
parent=child;
child=2*parent+1;
}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;
}
}
}
}
PriorityQueue是Java对堆的一个实现类,继承了Queue接口。
在Java中重写comparator方法可实现小根堆到大根堆的转换:
A=new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
常用方法:
函数名 | 功能介绍 |
---|---|
boolean offer(E e) | 插入元素e,插入成功返回true,e不能为空,会自动扩容。时间复杂度O(log2N)。 |
E peek() | 获取优先级最高的元素。 |
E poll() | 移除优先级最高的元素并返回。 |
int size() | 获取有效元素的个数 |
void clear() | 清空 |
boolean isEmpty() | 检测优先级队列是否为空。 |
优先级队列的扩容说明: 如果容量小于64时,是按照oldCapacity的2倍方式扩容的 如果容量大于等于64,是按照oldCapacity的1.5倍方式扩容的 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容
利用堆排序的思想解决TOP-K问题:
在数据量极大的情况下求数据集合中前K个最大的元素或者最小的元素。
因为此时数据太大,无法一次性全部加载到内存中,不能使用一般的排序方法来进行求解了,最佳方式用堆求解,思路如下:
1.用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2.用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。