优先级队列---java---黑马

优先级队列

双端队列、队列、栈对比

	定义	特点
队列	一端删除(头)，另一端添加(尾)	First In First Out
栈	一端删除和添加	First In Last Out
双端队列	两端都可以添加和删除
优先级队列		优先级高先出队
延时队列		根据延时时间确定优先级
并发非阻塞队列	队列空或满时不阻塞
并发阻塞队列	队列空时删除阻塞，队列满时添加阻塞

队列接口实现

public interface Queue<E> {boolean offer(E value);E poll();E peek();boolean isEmpty();boolean isFull();
}

public interface Priority {// 返回对象优先级，数字越大，优先级越高int priority();
}

基于无序数组实现

public class PriorityQueue1<E extends Priority> implements Queue<E> {Priority[] array;int size;public PriorityQueue1(int capacity) {this.array = new Priority[capacity]; }@Override		// 数组尾部添加元素，时间复杂度为O(1)public boolean offer(E value) {if (isFull()) {return false;}array[size++] = value;return true;}public int selectMax() {int max = 0;for(int i = 1; i < size; i++) {if (array[i].priority() > array[max].priority()) {max = i;}}return max;}@Override		// 移除优先级高的元素，时间复杂度为O(n)public E poll() {if (isEmpty()) {return null;}int index = selectMax();E value = (E) array[index];remove(index);return value;}public void remove(int index) {if (index < size - 1) {System.arraycopy(array, index + 1, array, index, size - index - 1);}size--;}@Override		// 得到优先级高的元素，时间复杂度为O(n)public E peek() {if (isEmpty()) {return null;}int index = selectMax();return (E) array[index];}@Overridepublic boolean isEmpty(){return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}
}

基于有序数组实现

public class PriorityQueue2<E extends Priority> implements Queue<E> {Priority[] array;int size;public PriorityQueue1(int capacity) {this.array = new Priority[capacity]; }@Override		// 数组尾部添加元素，时间复杂度为O(n)public boolean offer(E value) {if (isFull()) {return false;}insert(value);size++;return true;}private void insert(E value) {int i = size - 1;while (i >= 0 && array[i].priority() > value.priority()) {array[i + 1] = array[i];i--;}array[i + 1] = value;}@Override		// 移除优先级高的元素，时间复杂度为O(1)public E poll() {if (isEmpty()) {return null;}E value = (E) array[size - 1];size--;array[size] = null;return value;}@Override		// 得到优先级高的元素，时间复杂度为O(1)public E peek() {if (isEmpty()) {return null;}return (E) array[size - 1];}@Overridepublic boolean isEmpty(){return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}
}

堆

定义

堆是一种基于树得数据结构，通过用完全二叉树实现。堆的特性如下：

• 在大顶堆中，任意节点C与它的父节点P符合，$P.vlaue\ge C.value$ 。
• 在小顶堆中，任意节点C与它的父节点P符合，$P.vlaue\le C.value$ 。
• 最顶层的节点(没有父亲)，称之为 $root$ 根节点。

特征

• 如果从索引0处开始存储节点数据
  • 节点 $i$ 的父节点为 $floor((i-1)/2)$ ，当 $i>0$ 时
  • 节点 $i$ 的左子节点为 $2i+1$ ，右子节点 $2i+2$ ，当然它们得 $<size$
• 如果从索引1处开始存储节点数据
  • 节点 $i$ 的父节点为 $floor(i/2)$ ，当 $i>0$ 时
  • 节点 $i$ 的左子节点为 $2i$ ，右子节点 $2i+1$ ，当然它们得 $<size$

堆实现优先级队列

public class PriorityQueue3<E extends Priority> implements Queue<E> {Priority[] array;int size;public PriorityQueue1(int capacity) {this.array = new Priority[capacity]; }@Override		// 数组尾部添加元素，时间复杂度为O(n)public boolean offer(E value) {if (isFull()) {return false;}int child = size++;int parent = (child - 1) / 2; while (child > 0 && value.priority() > array[parent].priority()) {array[child] = array[parent];child = parent;parent = (child - 1) / 2;}array[child] = value;return true;}private void insert(E value) {int i = size - 1;while (i >= 0 && array[i].priority() > value.priority()) {array[i + 1] = array[i];i--;}array[i + 1] = value;}@Override		// 移除优先级高的元素，时间复杂度为O(1)public E poll() {if (isEmpty()) {return null;}swap(0, size - 1);size--;E value = array[size];array[size] = null;//下潜down(0);return value;}private void down(int parent) {int left = 2 * parent + 1;int right = left + 1;int max = parent;if (array[left].priority() > parent.priority()) {max = left;}if (array[right].priority() > parent.priority()) {max = right;}if (max != parent) {swap(max, parent);down(max);}}@Override		// 得到优先级高的元素，时间复杂度为O(1)public E peek() {if (isEmpty()) {return null;}return (E) array[0];}private void swap(int i, int j) {Priority t = array[i];array[i] = array[j];array[j] = t;}@Overridepublic boolean isEmpty(){return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}
}