上海微网站制作建设,有哪些做的好看的网站吗,wordpress最新文章插件,修邦建设网站#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 优先级队列说明 2.0 用数组实现优先级队列 3.0 无序数组实现优先级队列 3.1 无序数组实现优先级队列 - 入队列 offer(E value) 3.2 无序数组实现优先级队列 - 出… 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 优先级队列说明 2.0 用数组实现优先级队列 3.0 无序数组实现优先级队列 3.1 无序数组实现优先级队列 - 入队列 offer(E value) 3.2 无序数组实现优先级队列 - 出队列 poll() 3.3 无序数组实现优先级队列 - 查看队列中优先级最大的元素 peek() 3.4 无序数组实现优先级队列 - 判断是否为空队列 3.5 无序数组实现优先级队列 - 判断是否为满队列 3.6 无序数组实现优先级队列完整代码 4.0 有序数组实现优先级队列 4.1 有序数组实现优先级队列 - 入队列 offer(E value) 4.2 有序数组实现有序队列 - 出队列 poll() 4.3 有序数组实现有序队列 - 查看优先级最大的元素 peek() 4.4 有序数组实现优先级队列 - 判断队列是否为空 4.5 有序数组实现优先级队列 - 判断队列是否为满队列 4.6 有序数组实现优先级队列完整代码 5.0 大顶堆实现优先级队列 5.1 堆实现优先级队列 - 入队列 offer(E value) 5.2 堆实现优先级队列 - 出队列 poll() 5.3 堆实现优先级队列 - 查看优先级最大的元素 peek() 5.4 堆实现优先级队列 - 判断该队列是否为空 5.5 堆实现优先级队列 - 判断该队列是否为满队列 5.6 堆实现优先级队列完整代码 1.0 优先级队列说明 优先级队列是一种特殊的队列其中每个元素都有一个优先级。在优先级队列中具有最高优先级的元素首先被移除。这与普通队列不同普通队列是先进先出FIFO的而优先级队列则是按照优先级来确定元素的出队顺序。 优先级队列通常用于需要按照优先级处理元素的场景比如任务调度、事件处理等。它可以使用不同的数据结构来实现最常见的是使用堆heap来实现优先队列。堆是一种特殊的树形数据结构它可以快速找到并移除具有最高或最低优先级的元素。 优先级队列的常见操作包括插入元素、移除具有最高优先级的元素、查看具有最高优先级的元素等。实现优先级队列的常见算法包括插入时的堆调整、移除最高优先级元素后的堆调整等。 2.0 用数组实现优先级队列 可以使用数组来实现优先级队列一种简单的实现方式是使用数组来存储元素并且按照优先级顺序来维护数组。 用数组实现优先级队列可分为两种无序数组实现、有序数组实现。 3.0 无序数组实现优先级队列 可以直接简单粗暴来说无序数组就是插入元素的时候不按照优先级进行排序而出队列的时候严格按照优先级大小进行出队列。 首先需要实现队列中的接口。比如入队列、出队列等。
接口代码如下 public interface QueueE {/*** 入队操作*/boolean offer(E value);/*** 出队操作*/E poll();/*** 查看队头元素*/E peek();/*** 判断是否为空队列*/boolean isEmpty();/*** 判断是否为满队列*/boolean isFull();
} 再接着设置优先级元素。
代码如下 public interface Priority {int priority();} public class Entry implements Priority{String string;int priority;public Entry(String string, int priority) {this.string string;this.priority priority;}Overridepublic int priority() {return priority;}Overridepublic String toString() {return Entry{ string string \ , priority priority };}
} 该设置的优先级元素需要实现 priority 接口返回当前优先级的大小。 成员变量有 Priority[] arr 自定义大小的数组、size 标记当前元素的个数。
代码如下 public class UnorderedPriorityQueueE extends Priority implements QueueE {private Priority[] arr;private int size;public UnorderedPriorityQueue(int capacity) {arr new Priority[capacity];}} 3.1 无序数组实现优先级队列 - 入队列 offer(E value) 由于用无序数组实现元素可直接在数组尾部入队列。
代码如下 Overridepublic boolean offer(E value) {if (isFull()) {return false;}arr[size] value;return true;} 注意在入队前需要判断是否为满队列。入队完后需要进行 size 。 3.2 无序数组实现优先级队列 - 出队列 poll() 根据元素的优先级大小进行出队列首先需要遍历数组找到索引为 i 处优先级最大的元素。一般有两种情况 第一种情况在索引为 i size - 1 处找到优先级最大的元素此时只需要将 size-- 然后将其引用置为空 arr[size] null 。 第二种情况不在索引为 i ! size - 1 处找到优先级最大的元素。那么需要将索引为 i 的元素被 i 1 处的元素进行覆盖长度为size - 1 - i 。
代码如下 Overridepublic E poll() {if (isEmpty()) {return null;}//先找到优先级大的点int j 0;for (int i 1; i size; i) {if (arr[j].priority() arr[i].priority()) {j i;}}E ret (E)arr[j];if (j size - 1) {System.arraycopy(arr,j1,arr,j,size - 1 - j);}size--;arr[size] null;return ret;} 最后需要返回优先级最大的元素在被置为 null 之前将其进行保存。每次出队完毕后需要进行 size-- 、置为 null 。 3.3 无序数组实现优先级队列 - 查看队列中优先级最大的元素 peek() 相比与出队列找到了优先级最大的元素后不需要进行删除该优先级最大的元素。
代码如下 Overridepublic E peek() {if (isEmpty()) {return null;}//先找到优先级大的点int j 0;for (int i 1; i size; i) {if (arr[j].priority() arr[i].priority()) {j i;}}E ret (E)arr[j];return ret;} 注意在查看元素之前需要先判断是否为空队列。 3.4 无序数组实现优先级队列 - 判断是否为空队列 若 size 0 则为空队列若不是则不为空。
代码如下 Overridepublic boolean isEmpty() {return size 0;}3.5 无序数组实现优先级队列 - 判断是否为满队列 若 size arr.length 时则为满队列若不相等则不为满。
代码如下 Overridepublic boolean isFull() {return size arr.length;} 3.6 无序数组实现优先级队列完整代码 public class UnorderedPriorityQueueE extends Priority implements QueueE {private Priority[] arr;private int size;public UnorderedPriorityQueue(int capacity) {arr new Priority[capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}arr[size] value;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}//先找到优先级大的点int j 0;for (int i 1; i size; i) {if (arr[j].priority() arr[i].priority()) {j i;}}E ret (E)arr[j];if (j size - 1) {System.arraycopy(arr,j1,arr,j,size - 1 - j);}size--;arr[size] null;return ret;}Overridepublic E peek() {if (isEmpty()) {return null;}//先找到优先级大的点int j 0;for (int i 1; i size; i) {if (arr[j].priority() arr[i].priority()) {j i;}}E ret (E)arr[j];return ret;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size arr.length;}
} 4.0 有序数组实现优先级队列 相对于无序数组优先级队列来说有序数组实现优先级队列入队列操作需要按照优先级大小进行插入而出队列操作直接在索引为 size - 1 处直接获取该最大优先级元素。 首先同样的需要实现队列中的接口。比如入队列、出队列等。
接口代码如下 public interface QueueE {/*** 入队操作*/boolean offer(E value);/*** 出队操作*/E poll();/*** 查看队头元素*/E peek();/*** 判断是否为空队列*/boolean isEmpty();/*** 判断是否为满队列*/boolean isFull();
} 再接着设置优先级元素。
代码如下 public class Entry implements Priority{String string;int priority;public Entry(String string, int priority) {this.string string;this.priority priority;}Overridepublic int priority() {return priority;}Overridepublic String toString() {return Entry{ string string \ , priority priority };}
} 成员变量有 Priority[] arr 自定义大小的数组、size 标记当前元素的个数。
代码如下 public class OrderedPriorityQueueE extends Priority implements QueueE{private Priority[] arr;private int size;public OrderedPriorityQueue(int capacity) {arr new Priority[capacity];}} 4.1 有序数组实现优先级队列 - 入队列 offer(E value) 使用有序数组实现优先级入队列在入队列之前从后往前遍历数组找到优先级小于入队列的元素优先级找到即可插入其中。
代码如下 Overridepublic boolean offer(E value) {if (isFull()) {return false;}//先找到优先级比value的优先级大的索引int i size - 1;while (i 0 arr[i].priority() value.priority()) {arr[i1] arr[i];i--;}arr[i1] value;size;return true;} 考虑一种情况若 size 0 时为空队列的时候该代码有无错误 答案是没有问题的当 size 0 时 则 i 0 - 1i -1 此时不会进入循环直接跳到 arr[i 1] 处所以在这种情况下该代码没有问题。 4.2 有序数组实现有序队列 - 出队列 poll() 这就相对于有序数组入队列来说比较简单了直接在索引为 i size - 1 处得到优先级最大的元素然后将 size-- 再接着 arr[size] 置为 null 。
代码如下 Overridepublic E poll() {if (isEmpty()) {return null;}E str (E)arr[size - 1];size--;arr[size] null;return str;} 注意需要记录优先级最大的元素并且返回。在出队列之前需要判断该队列是否为空队列。 4.3 有序数组实现有序队列 - 查看优先级最大的元素 peek() 先判断该队列是否为空队列若不是直接返回该数组索引为 size - 1 处的元素即可。
代码如下 Overridepublic E peek() {if (isEmpty()) {return null;}E str (E)arr[size - 1];return str;} 4.4 有序数组实现优先级队列 - 判断队列是否为空 若 size 0 则为空若不为则为不空。
代码如下 Overridepublic boolean isEmpty() {return size 0;} 4.5 有序数组实现优先级队列 - 判断队列是否为满队列 若 size arr.length 时则为满队列若不是则为不满队列。
代码如下 Overridepublic boolean isFull() {return size arr.length;} 4.6 有序数组实现优先级队列完整代码 public class OrderedPriorityQueueE extends Priority implements QueueE{private Priority[] arr;private int size;public OrderedPriorityQueue(int capacity) {arr new Priority[capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}//先找到优先级比value的优先级大的索引int i size - 1;while (i 0 arr[i].priority() value.priority()) {arr[i1] arr[i];i--;}arr[i1] value;size;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E str (E)arr[size - 1];size--;arr[size] null;return str;}Overridepublic E peek() {if (isEmpty()) {return null;}E str (E)arr[size - 1];return str;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size arr.length;}
} 5.0 大顶堆实现优先级队列 大顶堆说明 大顶堆是一种特殊的堆它是一种完全二叉树其中每个父节点的值都大于或等于其左右子节点的值。在大顶堆中根节点的值是整个堆中最大的。 大顶堆可以使用数组来实现其中堆的根节点存储在数组的第一个位置然后按照完全二叉树的性质依次存储其他节点。这种实现方式使得大顶堆的父节点和子节点之间可以通过简单的数学关系来计算从而方便进行堆调整操作。假设 i 不为 0 该双亲索引为i - 1/ 2 该左孩子为2 * i 1该右孩子为2 * i 2 。 首先需要实现队列中的接口。比如入队列、出队列等。
接口代码如下 public interface QueueE {/*** 入队操作*/boolean offer(E value);/*** 出队操作*/E poll();/*** 查看队头元素*/E peek();/*** 判断是否为空队列*/boolean isEmpty();/*** 判断是否为满队列* */boolean isFull();
} 再接着设置优先级元素。
代码如下 public class Entry implements Priority{String string;int priority;public Entry(String string, int priority) {this.string string;this.priority priority;}Overridepublic int priority() {return priority;}Overridepublic String toString() {return Entry{ string string \ , priority priority };}
} 成员变量有 Priority[] arr 自定义大小的数组、size 标记当前元素的个数。
代码如下 public class BigTopPileE extends Priority implements QueueE {private Priority[] arr;private int size;public BigTopPile(int capacity) {arr new Priority[capacity];}} 5.1 堆实现优先级队列 - 入队列 offer(E value) 具体思路为由于是按照优先级大小来存放元素的所以需要先比较优先级大小在适合的位置插入。现在已知 i size该双亲为i - 1/ 2 。接下来需要判断 arr[i - 1/ 2] 的优先级于入队列的元素优先级大小若 arr[i - 1/ 2] 的优先级较大此时该入队列的元素存放的位置为 arr[i] value 若 value 的优先级大于当前 arr[i - 1/ 2] 时先将当前 arr[i - 1/ 2] 往后放即 arr[i] arr[i - 1/ 2] 。之后需要继续往上找双亲将 i (i - 1) / 2 直到 i 0 或者 value 的优先级小于当前 arr[i - 1/ 2] 时则为 arr[i] value 。
代码如下 Overridepublic boolean offer(E value) {if (isFull()) {return false;}int i size;int j (i - 1) / 2;while (i 0 arr[j].priority() value.priority()) {arr[i] arr[j];i j;j (i - 1) / 2;}arr[i] value;size;return true;} 只要 i 0 时 j 不能继续往上走了否则为抛空指针异常。 5.2 堆实现优先级队列 - 出队列 poll() 具体思路为分为两步。 第一步将 arr[size - 1] 处的元素交换到 arr[0] 处。 第二步由于根处的优先级永远都要大于该孩子的优先级所以将交换之后的元素进行下潜即先找到该左右孩子优先级最大的元素于根元素进行交换一直往下进行下潜。直到该根元素没有左右孩子或者根元素的优先级都大于该左右孩子的优先级。
代码实现 非递归实现 Overridepublic E poll() {if (isEmpty()) {return null;}E top (E)arr[0];arr[0] arr[size - 1];size--;arr[size] null;int i 0;while ( (i * 2 1) size (i * 2 2) size (arr[i].priority() arr[i * 2 1].priority() || arr[i].priority() arr[i * 2 2].priority() ) ) {int j 0;if (arr[i * 2 1].priority() arr[i * 2 2].priority()) {j i * 2 1;}else if (arr[i * 2 1].priority() arr[i * 2 2].priority()) {j i * 2 2;}E temp (E)arr[j];arr[j] arr[i];arr[i] temp;i j;}return top;} (i * 2 1) size (i * 2 2) size 该代码判断的是有无左右孩子元素。 递归实现 public E poll1() {if (isEmpty()) {return null;}//交换头尾swap(0,size - 1);size--;//置为 nullE ret (E)arr[size];arr[size] null;//下潜down(0);return ret;}private void swap(int i, int j) {E t (E)arr[i];arr[i] arr[j];arr[j] t;}private void down(int i) {int left 2 * i 1;int right 2 * i 2;int max i;if ( left size arr[max].priority() arr[left].priority()) {max left;}if (right size arr[max].priority() arr[right].priority()) {max right;}if (max ! i) {swap(max,i);down(max);}} 5.3 堆实现优先级队列 - 查看优先级最大的元素 peek() 先判断该队列是否为空若不为空则直接返回堆顶元素即可。
代码如下 Overridepublic E peek() {if (isEmpty()) {return null;}return (E)arr[0];} 5.4 堆实现优先级队列 - 判断该队列是否为空 当 size 0 时则为空队列。
代码实现 Overridepublic boolean isEmpty() {return size 0;} 5.5 堆实现优先级队列 - 判断该队列是否为满队列 当 size arr.length 时则为满队列。
代码实现 Overridepublic boolean isFull() {return size arr.length;} 5.6 堆实现优先级队列完整代码 public class BigTopPileE extends Priority implements QueueE {private Priority[] arr;private int size;public BigTopPile(int capacity) {arr new Priority[capacity];}Overridepublic boolean offer(E value) {if (isFull()) {return false;}int i size;int j (i - 1) / 2;while (i 0 arr[j].priority() value.priority()) {arr[i] arr[j];i j;j (i - 1) / 2;}arr[i] value;size;return true;}Overridepublic E poll() {if (isEmpty()) {return null;}E top (E)arr[0];arr[0] arr[size - 1];size--;arr[size] null;int i 0;while ( (i * 2 1) size (i * 2 2) size (arr[i].priority() arr[i * 2 1].priority() || arr[i].priority() arr[i * 2 2].priority() ) ) {int j 0;if (arr[i * 2 1].priority() arr[i * 2 2].priority()) {j i * 2 1;}else if (arr[i * 2 1].priority() arr[i * 2 2].priority()) {j i * 2 2;}E temp (E)arr[j];arr[j] arr[i];arr[i] temp;i j;}return top;}public E poll1() {if (isEmpty()) {return null;}//交换头尾swap(0,size - 1);size--;//置为 nullE ret (E)arr[size];arr[size] null;//下潜down(0);return ret;}private void swap(int i, int j) {E t (E)arr[i];arr[i] arr[j];arr[j] t;}private void down(int i) {int left 2 * i 1;int right 2 * i 2;int max i;if ( left size arr[max].priority() arr[left].priority()) {max left;}if (right size arr[max].priority() arr[right].priority()) {max right;}if (max ! i) {swap(max,i);down(max);}}Overridepublic E peek() {if (isEmpty()) {return null;}return (E)arr[0];}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size arr.length;}
}
