奈曼旗华水建设工程公司网站,招聘企业网站建设模块,软件开发必备编程工具,宝安附近公司做网站建设哪家效益快优先队列 API初级实现使用堆实现由下至上的堆有序化#xff08;上浮#xff09;由上至下的堆有序化#xff08;下沉#xff09;插入和删除元素具体实现 很多情况下我们需要有序的处理输入的元素#xff0c;但是又不需要输入的元素全部有序#xff0c;或者不需要一次将它们… 优先队列 API初级实现使用堆实现由下至上的堆有序化上浮由上至下的堆有序化下沉插入和删除元素具体实现 很多情况下我们需要有序的处理输入的元素但是又不需要输入的元素全部有序或者不需要一次将它们排序出来。还有的情况的输入的元素不是一次性给出的需要我们根据需要实时获取最大值或者最小值。这时候我们就可以使用优先队列实现我饿们的需求。 API
public class MaxPQ Key extends ComparableKeyMaxPQ()创建一个优先队列MaxPQ(int max)创建一个初始容量为max的优先队列MaxPQ(Key[] a)用a[]中的元素创建一个优先队列void insert(Key v)向优先队列中插入一个元素Key max()返回最大元素Key delMax()删除返回最大元素boolean isEmpty()返回队列是否为空int size()返回优先队列中元素个数
初级实现
初级实现是使用一个数组或者链表在插入时或者获取最大元素动态维护数组或者链表的有序性并使得调用对应获取最大值的API能正确获取结果。
使用堆实现 当一棵二叉树的每个结点都大于等于它的两个子节点时它被称为堆有序。根节点是堆有序的二叉树中的最大结点。二叉堆是一组能够用堆有序的完全二叉树排序的元素并在数组中按照层级存储不使用数组的第一个位置 由下至上的堆有序化上浮
如果堆有序的状态因为某个节点变得比它的父节点更大而被打破那么我们就需要通过交换它和它的父节点来修复堆。交换后这个节点比它的两个子节点都打但这个节点仍然可能比它现在的父节点更大。我们可以一遍遍地使用同样地办法恢复秩序将这个节点不断向上移动直到我们遇到一个更大的父节点。
private void swim(int k) {while (k 1 less(k / 2, k)) {exch(k/2, k);k / 2;}
}由上至下的堆有序化下沉
如果堆有序状态因为某个结点变得比它的两个子节点或是其中之一更小而被打破了那么我们可以通过将它和它的两个子节点中的较大者交换来恢复堆。交换可能会在子节点处继续打破堆的有序状态因此我们需要不断地用相同的方式将其修复将节点下移直到它的子节点都比它更小或者到达了堆的底部。
private void sink(int k) {while (2 * k N) {int j 2 * k;if (j n less(j, j 1)) j;if (!less(k, j)) break;exch(k, j);k j;}
}插入和删除元素
插入新元素我们将新元素添加到数组末尾增加堆的大小并让这个新元素上浮到合适的位置。 删除最大元素我们将数组顶端删去最大的元素并将数组的最后一个元素放到顶端减小堆的大小并让这个元素下沉到合适的位置。
具体实现
public class MaxPQ Key extends ComparableKey {private Key[] pq;private int N 0;public MaxPQ(int maxN) {pq (Key[]) new Comparable[maxN 1];}public boolean isEmpty() {return N 0;}public int size() {return N;}public void insert(Key v) {pq[N] v;swim(N);}public Key delMax() {Key max pq[1];exch(1, N--);pq[N 1] null;sink(1);return max;}private boolean less(int i, int j)private void exch(int i, int j)private void swim(int k)private void sink(int k)
}对于一个含有N个元素的基于堆的优先队列插入元素操作只需不超过(logN 1)次比较删除最大元素的操作需要不超过2logN次比较
