简单解释优先队列,即为在队列之中呢,元素被赋予了优先级,实现了优先级高的先出.
对于其,我们先定义API接口
常见方法: delMax()删除最大元素 insert()插入元素
还有比较元素 less()
对于其实现
可以分别使用4种基本数据结构是实现优先队列的起点,可以分别使用有序的或者无序的数组或者链表去实现,
1.无序数组实现
实现删除最大元素的时候,我们添加一段类似选择排序的内循环,让最大元素和边界交换并删除
2.有序数组实现
在insert中添加diamante,使较大的元素都向右移动以一格,方便我们之后方法的调用
3.链表实现
基于链表的下压栈,然后修改pop来返回最大元素
最有的实现方式,是我们使用二叉堆来实现优先队列
二叉堆本质上是一个二叉树,每个父结点都要大于等于两个子节点,这就是堆有序
根节点是其最大的结点
二叉堆的顺序可以为,自上而下,自左往右,在每个结点下面连接两个小的节点.
每个元素都有三个节点,一个父节点和两个子节点
实现它的方法很简单,只要一个数组,根节点在索引1,其子节点在 2,3,子节点的子节点在5,6,7
二叉树构造的数组索引0位置不使用
二叉树的结构很严格,但我们仍可以实现插入元素和删除最大元素
如果堆的有序性因为某个结点的变化而改变
结点变得更大,就循环交换他和他的父节点来修复堆结构,
我们称为上浮;
如果结点变得更小,就循环交换他和他的子节点来修复堆结构,
对应的就是下沉
删除最大元素的时候,直接让最大元素和最小的元素进行交换并删除,这样打破了规则,然后我们重新下沉排序
|
public class Priority_Queue_Binary_Tree<Key extends Comparable<Key>>{
private Key[] pq;//静态数组 private int N = 0; public void MaxPQ(int maxN) { pq = (Key[])new Comparable[maxN+1];//创建一个 大于N 1的数组 N = maxN;//N为数组的数量 } public boolean isEmpty() { return N==0; } public int size() { return N; } public void insert(Key input) {//插入 pq[++N] = input; swim(N);//进行排序 } public Key delMax(){//输出最大 Key max = pq[1];//获取 exch(pq, 1, N–);//交换 pq[N++] = null;//防止溢出 sink(1);//向下排序 return max;//输出 } private void swim(int k) { while(k>1&&less(pq[k/2], pq[k])) {//如果大于1,且比父节点大 exch(pq, k/2, k);//交换 k = k/2;//递归 } } private void sink(int k) { while (2*k<=N) {//子节点小于数组 int j= 2*k; if (j<N &&less(pq[j], pq[j+1])) {//只要不溢出且比子节点小 j++;//加大索引 } while (!less(pq[k], pq[j])) break;//如果大于则退出 exch(pq, k, j);//交换 k = j;//然后递归 } } public static boolean less(Comparable a, Comparable a2) {// 对元素进行比较 return a.compareTo(a2) < 0; } private static void exch(Comparable[] a, int i, int j) {// 进行交换 Object n = a[i]; a[i] = a[j]; a[j] = (Comparable<Object>) n; } } |
他的插入和删除实现即:
插入时候直接插到最后面,然后上浮
删除则是最后一个和第一个进行交换,然后输入原第一位的最大元素,
把现第一位的元素进行下沉,还把N+1的值设置为Null,进行收回空间