数据结构——优先级队列和堆

1.让parent标记需要调整的节点child标记parent的左孩子注意parent如果有孩子一定先是有左孩子

2.如果parent的左孩子存在child<size则进行以下操作直到parent的左孩子不存在
   1.parent右孩子是否存在存在找到左右孩子中的最小值让child进行标记
   2.将parent与较小的孩子child进行比较
       【1】.parent小于较小的孩子child时结束调整
       【2】.parent大于较小的孩子child时交换parent与child的值。此时可能并不正确因此需要继续向下调整即parent=childchild=parent*2+1然后重复上述过程

public void shiftDown(int parent,int len){
	int child=2*parent+1;
	while(child<size){
		if(child+1<size&&elem[child+1]<elem[child]){
			child+=1;
		}
		if(elem[parent]<=elem[child]){
			break;
		}else{
			int tmp=elem[parent];
			elem[parent]=elem[child];
			elem[child]=tmp;
			parent=child;
			child=parent*2+1;
		}
	}
}

注意在整个向下调整的过程中时间复杂度为O (log2N).

【2】.向上调整

1.让child标记需要调整的节点然后找到child的双亲节点parent。

2.如果双亲节点parent存在chid>0则进行以下操作直到双亲节点不存在

1.将双亲节点与孩子节点进行交换
【1】.如果双亲节点比孩子节点小parent满足堆的性质调整结束
【2】.双亲节点大于孩子节点时交换parent与child的值。此时可能并不正确因此需要继续向上调整即child=parent; parent=(child-1)/2; 然后重复上述过程。

public void shiftUp(int child){
	int parent =(child-1)/2;
	while(child>0){
		if(elem[parent]>elem[child]){
			break;
		}else{
			int tmp=elem[parent];
			elem[parent]=elem[child];
			elem[child]=tmp;
			child=parent;
			parent=(child-1)/2;
		}
	}
}

注意在整个向上调整的过程中时间复杂度为O (N).

2.堆的创建

public class Heap{
	public int[] elem;
	public int usedSize;
	public Heap(){
		this.elem=new int[10];
	}
	public void initElem(int[] arr){
		for(int i=0;i<arr.length;i++){
			elem[i]=arr[i];
			usedSize++;
		}
	}
	public void createHeap(){
		for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
			shiftDown(parent,usedSize);
		}
	}
}

3.建堆的时间复杂度

注意因为堆是完全二叉树而满二叉树也是完全二叉树因此简化为满二叉树来证明。

4.堆的插入和删除

注意堆的插入和删除时间复杂度均为Olog2N

【1】.堆的插入

步骤
1.将元素放到最后一个元素后边空间不够时需要扩容。
2.将最后新插入的节点向上调整直到满足要求。

public void push(int val){
	if(isFull()){
		elem=Arrays.copyOf(elem,2*elem.length);
	}
	elem[usedSize++]=val;
	shiftUp(usedSize-1);
}
public boolean isFull(){
    return usedSize==elem.length;
}

【2】.堆的删除

步骤
   1.将堆顶元素与堆中最后一个元素交换。
   2.将堆中元素有效数据个数减少一个。
   3.对堆顶元素进行向下调整。

public void pop(){
	if(isEmpty()){
		return;
	}
	int tmp=elem[0];
	elem[0]=elem[usedSize-1];
    	elem[usedSize-1]=tmp;
	usedSize--;
	shiftDown(0,usedSize);
}
public boolean isEmpty(){
	return usedSize==0;
}

5.堆的应用

1.PriorityQueue的实现

用堆作为底层结构封装优先级队列

2.堆排序

堆排序是利用堆的思想进行排序首先需要建一个堆升序排序建大堆降序排序建小堆其次利用堆删除思想来进行排序

public void HeapSort(){
	int end=usdSize-1;
	while(end>0){
		swap(elem,0,end);
		shiftDown(0,end);
		end--;
	}
}

3.Top-k问题

求数据集合中前K个最大的元素或最小的元素一般情况下数据量比较大普通排序就不可取因此我们就需要用到堆来排序。

首先用数据集合中前K个元素建堆求K个最大元素建小堆求K个最小元素建大堆然后用剩余的N-K个元素依次与堆顶元素比较堆顶元素不满足则替换。

二、优先级队列

1.概念

队列是一种先进先出的数据结构但有时操作的数据会带有优先级所以在出队列时可能需要优先级较高的的元素先出队列。因此数据结构需要提供返回最高优先级对象和添加新对象这两个基本操作这种数据结构就是优先级队列。

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列。PriorityQueue是线程不安全的而PriorityBlockingQueue是线程安全的本文重点讲解PriorityQueue。

2.PriorityQueue详解

1.常用接口

2.PriorityQueue的构造方法

【1】.PriorityQueue()创建一个空的优先级队列默认容量是11

PriorityQueue<Integer> priorityqueue = new PriorityQueue<>();

【2】.PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列注意initialCapacity不能小于1否则会抛出IllegalArgumentException异常

PriorityQueue<Integer> priorityqueue = new PriorityQueue<>(100);

【3】.PriorityQueue(Collection<?extends E> c) 用一个集合来创建优先级队列

ArrayList<Integer> arraylist = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
PriorityQueue<Integer> priorityqueue = new PriorityQueue<>(arraylist);

3.常用函数

boolean offer(E e)

插入元素e插入成功返回true如果e对象为空抛出NullPointerException异常时间复杂度注意空间不够时候会进行扩容。

E peek()

获取优先级最高的元素如果优先级队列为空返回null

E poll()

移除优先级最高的元素并返回如果优先级队列为空返回null

int size()

获取有效元素的个数

void clear()

清空

boolean isEmpty()

检测优先级队列是否为空空返回true

4.扩容

如果容量小于64时是按照oldCapacity的2倍方式扩容的。
如果容量大于等于64是按照oldCapacity的1.5倍方式扩容的。
如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容。

5.注意

【1】.PriorityQueue中放置的元素必须要能比较大小不能插入无法比较大小的否则会抛出ClassCastException异常

【2】.不能插入null对象否则会抛出NullPointerException

【3】.没有容量限制可以插入任意多个元素其内部可以自动扩容

【4】.插入和删除元素的时间复杂度为Olog2N

【5】.PriorityQueue底层使用了堆数据结构

【6】.PriorityQueue默认是小堆如果需要大堆需要用户提供比较器

// 自定义比较器直接实现Comparator接口然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
	@Override
	public int compare(Integer o1, Integer o2) {
		return o2-o1;
	}
}

三、优先队列PriorityQueue和堆Heap的区别

优先队列是一种特殊的队列

堆是一个很大的概念并不一定是完全二叉树在前文中使用完全二叉树是因为这个很容易被数组储存所以大部分我们用完全二叉树数组来储存堆但是除了这种二叉堆之外我们还有二项堆、斐波那契堆等这些堆就不属于二叉树。

优先对列和堆有什么区别呢这里说的堆默认是我们最常使用的二叉堆而二叉堆只是优先队列的一种是实现方式而已。而优先队列还有二项堆、平衡树、线段树等来实现。所以说优先队列和堆不是一个概念如果非要说他们之间的关系就是二叉堆只是优先队列的一种实现方式而java的PriorityQueue也是基于这个实现的。