建站公司如何在抖音平台开店,在家来料加工,东莞公司网站制作,赶集网官网首页文章目录 优先级队列#xff08;Priority Queue#xff09;实现方式基于数组实现基于堆实现方法实现offer(E value)poll()peek()isEmpty()isFull() 优先级队列的实现细节 优先级队列#xff08;Priority Queue#xff09; 优先级队列是一种特殊的队列#xff0c;其中的元素… 文章目录 优先级队列Priority Queue实现方式基于数组实现基于堆实现方法实现offer(E value)poll()peek()isEmpty()isFull() 优先级队列的实现细节 优先级队列Priority Queue 优先级队列是一种特殊的队列其中的元素不是按照进入队列的顺序出队而是按照元素的优先级出队。在优先级队列中元素的优先级最高的将会首先出队。 实现方式
基于数组实现
以下是基于数组的优先级队列的简单实现
public class PriorityQueueArrayE extends Priority {private E[] array;private int size 0;public PriorityQueueArray(int capacity) {array (E[]) new Object[capacity];}public boolean offer(E value) {if (size array.length) return false;int i size - 1;while (i 0 array[i].priority value.priority) {array[i 1] array[i];i--;}array[i 1] value;size;return true;}public E poll() {if (size 0) return null;E result array[size - 1];array[size - 1] null;size--;return result;}public E peek() {if (size 0) return null;return array[size - 1];}public boolean isEmpty() {return size 0;}public boolean isFull() {return size array.length;}
}这个实现中offer方法将元素插入到正确的位置以保持数组的有序性poll方法删除并返回优先级最高的元素peek方法返回但不删除优先级最高的元素。isEmpty和isFull方法分别用于检查队列是否为空或已满。
基于堆实现 基于数组的实现有一些缺点。例如插入和删除元素可能需要移动大量的元素特别是在最坏的情况下这可能需要移动整个数组。因此这种实现的时间复杂度可能会达到O(n)其中n是队列的大小。 这就是为什么在实践中我们通常会使用更复杂的数据结构如堆来实现优先级队列。使用堆实现的优先级队列可以在O(log n)的时间复杂度内插入和删除元素这比基于数组的实现更有效率。 优先级队列通常使用堆Heap数据结构来实现。在Java中可以通过实现Queue接口来创建一个优先级队列。下面的代码是一个使用最大堆实现的优先级队列
public class PriorityQueue2E extends Priority implements QueueE {Priority[] array;public int size;public PriorityQueue2(int capacity) {array new Priority[capacity];}...
}这个优先级队列中的元素必须实现Priority接口这个接口定义了元素的优先级。
方法实现
优先级队列通常包含以下方法
offer(E value)
将元素插入到优先级队列中。如果队列已满返回false否则将元素插入到正确的位置以保持堆的性质并返回true。
Override
public boolean offer(E value) {if(isFull())return false;if (size 0){array[0] value;}else{int child size;int partent (child - 1) / 2;while (child 0 value.priority array[partent].priority){array[child] array[partent];child partent;partent (child - 1) / 2;}array[child] value;}size;return true;
};poll()
移除并返回优先级最高的元素。如果队列为空返回null。
Override
public E poll() {if (isEmpty())return null;E result (E)array[0];array[0] array[size-1];array[size] null;size--;down(0);return result;
}private void down(int parent){int child1 parent * 2 1;int child2 parent * 2 2;if(child1 size )return;int maxIndex child2 size array[child2].priority array[child1].priority ? child2: child1;if(array[maxIndex].priority array[parent].priority)return;change(parent,maxIndex);down(maxIndex);
}private void change(int parent,int child){Priority p array[parent];array[parent] array[child];array[child] p;
}peek()
返回优先级最高的元素但不移除它。如果队列为空返回null。
Override
public E peek() {if (isEmpty())return null;return (E)array[0];
}isEmpty()
判断队列是否为空。
Override
public boolean isEmpty() {return size 0;
}isFull()
判断队列是否已满。
Override
public boolean isFull() {return size array.length;
}优先级队列的实现细节
优先级队列的实现主要基于一个堆结构。堆是一种特殊的完全二叉树其中每个节点的值都大于或等于其子节点的值最大堆或小于或等于其子节点的值最小堆。
在我们的实现中我们使用了一个数组array来存储堆的元素并使用size来记录堆的大小。这是因为完全二叉树可以非常方便地用数组来表示。具体来说对于数组中的任何一个元素其左子节点的索引是2 * index 1右子节点的索引是2 * index 2而其父节点的索引是(index - 1) / 2。
