目录
无序数组:
有序数组:
堆:
分析:
代码:
Entry类:
无序数组:
//基于无序数组实现的优先队列
public class PriorityQueue1 <E extends Priority> implements Queue<E> {//数组类型是priority;Priority[] array; //E extend Priorityint size;public PriorityQueue1(int capacity){array = new Priority[capacity];size = 0;}@Overridepublic boolean offer(E e) {if(isFull()){return false;}array[size++]=e;return true;}@Overridepublic E poll() {if(isEmpty()){return null;}int max=selectMax();int last=size-1;//交换E e =(E)array[max];remove(max);return (E) e;}private void remove(int index){if(index<size-1){System.arraycopy(array,index+1,array,index,size-1-index);//size-1是最后一个索引}array[--size]=null;}//返回优先级最高的索引值private int selectMax(){int max=0;for(int i=1;i<size;i++){if(array[i].priority()>array[max].priority()){max=i;}}return max;}@Overridepublic E peek() {if(isEmpty()){return null;}int max=selectMax();return (E) array[max];}@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 PriorityQueue2(int capacity){array = new Priority[capacity];}@Overridepublic 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;}@Overridepublic E poll() {if(isEmpty()){return null;}E e=(E) array[size-1];array[--size]=null;return e;}@Overridepublic E peek() {if(isEmpty()){return null;}return (E) array[size-1];}@Overridepublic boolean isEmpty() {return size==0;}@Overridepublic boolean isFull() {return size==array.length;}
}
堆:
分析:
* * 大顶堆:父节点的值比左右孩子的值大 * 小顶堆:父节点的值比左右孩子的值小 * 如果从索引0开始 * 节点i的父节点为floor(i-1)/2 前提i>0; 节点i的左子节点为2i+1,右子节点为2i+2 前提i<size * 如果索引从1开始 * 节点i的父节点为i/2 前提i>1; 节点i的左子节点为2i,右子节点为2i+1 前提i<size * */
offer:
1.入堆新元素,加入到数组的末尾(索引位置 child) * 2.将新元素与父节点比较,如果比父节点大,则交换位置,直到新元素不大于父节点,或者到达根节点
poll:
/* * 1.交换堆顶和堆尾元素,让尾部元素出队 * 2.从堆顶开始,将父元素与两个孩子较大者交换, * 直到父元素比两个孩子大,或者到达叶节点 * */
代码:
//大顶堆:优先级最高的为0索引
public class PriorityQueue3 <E extends Priority> implements Queue<E>{Priority [] array;int size;public PriorityQueue3(int capacity){array = new Priority[capacity];}@Overridepublic boolean offer(E value) {if(isFull()){return false;}int child=size++;int parent=(child-1)/2;while((child>0)&&(array[parent].priority()<value.priority())){array[child]=array[parent];child=parent;parent=(child-1)/2;}array[child]=value;return true;}@Overridepublic E poll() {if(isEmpty()){return null;}swap(0,--size);Priority e=array[size];array[size]=null;//堆化down(0);return (E) e;}private void down(int parent) {int left=2*parent+1;int right=2*parent+2;int max=parent;//假设父节点最大if(left<size&&array[left].priority()>array[max].priority()){max=left;}if(right<size&&array[right].priority()>array[max].priority()){max=right;}if(max!=parent){swap(max,parent);down(max);}}//交换private void swap(int i,int j){Priority temp=array[i];array[i]=array[j];array[j]=temp;}@Overridepublic E peek() {if(isEmpty()){return null;}return (E) array[0];}@Overridepublic boolean isEmpty() {return size==0;}@Overridepublic boolean isFull() {return size==array.length;}
}
Entry类:
public class Entry implements Priority{String value;int priority;public Entry(String value, int priority){this.value = value;this.priority = priority;}@Overridepublic int priority() {return priority;}@Overridepublic String toString() {return "(" +"value=" + value + '='+", priority=" + priority +')';}
}