基于堆的优先级队列
实现大顶堆的优先级队列：
import java.util.NoSuchElementException;
class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq; // 基于堆的完全二叉树
private int N; // 存储在pq[1..N]中，pq[0]没有使用
public MaxPQ(int maxN) {
if (maxN >= 0) {
pq = (Key[]) new Comparable[maxN + 1];
} else {
throw new IllegalArgumentException("Illegal Capacity: " + maxN);
}
}
public MaxPQ() {
this(10);
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert(Key v) {
if (N == pq.length - 1)
resize();
pq[++N] = v;
swim(N);
}
public Key delete() { // 大顶堆删除最大的
if (isEmpty())
throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1]; // 从根节点得到最大元素
swap(1, N); // 将其和最后一个结点交换
pq[N--] = null; // 便于垃圾回收
sink(1); // 恢复堆的有序性
return max;
}
private void sink(int k) {
while ((k << 1) <= N) { // j <= N说明一定有左孩子
int j = k << 1; // 左孩子下标
if (j < N && less(j, j + 1)) // j < N说明一定有右孩子,如果左孩子小于右孩子的值
++j; // 下标转移到右孩子
if (!less(k, j)) // 如果k结点的值不小于他的孩子中的最大值
break; // 已经无法继续下沉了，跳出
swap(k, j); // 下沉，和孩子中的最大值交换
k = j; // 现在这个元素已经在刚刚的j位置上，继续记录这个元素的位置，看能否继续下沉
}
}
private void swim(int k) {
// 如果不是第一个元素，并且第k个元素比父节点的值小，那么与父节点交换
while (k > 1 && less(k >> 1, k)) {
swap(k >> 1, k);
k >>= 1;
}
}
private void swap(int i, int k) {
Key t = pq[i];
pq[i] = pq[k];
pq[k] = t;
}
private boolean less(int i, int k) {
return pq[i].compareTo(pq[k]) < 0;
}
// ArrayList空参构造方法默认是空数组，第一次插入时会扩容，就比较size+1和10的最大值，扩容后为10
private void resize() { // 扩容逻辑简单模仿ArrayList
int capacity = N + (N >> 1);
if (capacity < N) // 如果溢出
capacity = N;
if (capacity > Integer.MAX_VALUE - 8) {
capacity = hugeCapacity(N);
}
Key[] temp = (Key[]) new Comparable[capacity];
for (int i = 1; i <= N; ++i) { // 扩容后复制到新数组
temp[i] = pq[i];
}
pq = temp;
}
private int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8;
}
}
public class MaxPriorityQueue {
public static void main(String[] args) {
MaxPQ<Integer> pq = new MaxPQ<Integer>();
pq.insert(5);
pq.insert(124);
pq.insert(456);
pq.insert(678);
pq.insert(2);
pq.insert(2);
pq.insert(6);
pq.insert(3);
pq.insert(88);
pq.insert(-45);
pq.insert(99);
int size = pq.size();
for (int i = 0; i < size; ++i) {
System.out.println(pq.delete());
}
}
}运行结果：
678
456
124
99
88
6
5
3
2
2
-45优先队列由一个基于堆的完全二叉树表示，存储于数组pq[1..N]中，pq[0]没有使用。在insert()中，我们将N加一并把新元素添加在数组最后，然后用swim()恢复堆的有序性（当一颗二叉树的结点都大于等于它的两个子节点时，它被称为堆有序）。在delete()中，我们从pq[1]中得到需要返回的元素，然后将pq[N]移动到pq[1]，将N减一，并用sink()恢复堆有序。同时我们还将不再使用的p[N]设置为null，以便系统回收它所占用的空间。
这里的主要逻辑是：
插入元素insert()：我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置。
删除最大元素delete()：我们从数组顶端删去最大元素pq[1]，就是先将数组的最后一个元素和顶端元素pq[1]交换，然后减小堆的大小N--(即删除数组最后一个元素)，并让顶端元素下沉到合适的位置。
同理可得：
实现小顶堆的优先级队列：
import java.util.NoSuchElementException;
class MinPQ<Key extends Comparable<Key>> {
private Key[] pq; // 基于堆的完全二叉树
private int N; // 存储在pq[1..N]中，pq[0]没有使用
public MinPQ(int maxN) {
if (maxN >= 0) {
pq = (Key[]) new Comparable[maxN + 1];
} else {
throw new IllegalArgumentException("Illegal Capacity: " + maxN);
}
}
public MinPQ() {
this(10);
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert(Key v) {
if (N == pq.length - 1)
resize();
pq[++N] = v;
swim(N);
}
public Key delete() { // 大顶堆删除最大的
if (isEmpty())
throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1]; // 从根节点得到最小元素
swap(1, N); // 将其和最后一个结点交换
pq[N--] = null; // 便于垃圾回收
sink(1); // 恢复堆的有序性
return max;
}
private void sink(int k) {
while ((k << 1) <= N) { // j <= N说明一定有左孩子
int j = k << 1; // 左孩子下标
if (j < N && greater(j, j + 1)) // j < N说明一定有右孩子,如果左孩子大于右孩子的值
++j; // 下标转移到右孩子
if (!greater(k, j)) // 如果k结点的值不大于他的孩子中的最大值
break; // 已经无法继续下沉了，跳出
swap(k, j); // 下沉，和孩子中的最小值交换
k = j; // 现在这个元素已经在刚刚的j位置上，继续记录这个元素的位置，看能否继续下沉
}
}
private void swim(int k) {
// 如果不是第一个元素，并且第k个元素比父节点的值小，那么与父节点交换
while (k > 1 && greater(k >> 1, k)) {
swap(k >> 1, k);
k >>= 1;
}
}
private void swap(int i, int k) {
Key t = pq[i];
pq[i] = pq[k];
pq[k] = t;
}
private boolean greater(int i, int k) {
return pq[i].compareTo(pq[k]) > 0;
}
// ArrayList空参构造方法默认是空数组，第一次插入时会扩容，就比较size+1和10的最大值，扩容后为10
private void resize() { // 扩容逻辑简单模仿ArrayList
int capacity = N + (N >> 1);
if (capacity < N) // 如果溢出
capacity = N;
if (capacity > Integer.MAX_VALUE - 8) {
capacity = hugeCapacity(N);
}
Key[] temp = (Key[]) new Comparable[capacity];
for (int i = 1; i <= N; ++i) { // 扩容后复制到新数组
temp[i] = pq[i];
}
pq = temp;
}
private int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8;
}
}
public class MinPriorityQueue {
public static void main(String[] args) {
MinPQ<Integer> pq = new MinPQ<Integer>();
pq.insert(5);
pq.insert(124);
pq.insert(456);
pq.insert(678);
pq.insert(2);
pq.insert(2);
pq.insert(6);
pq.insert(3);
pq.insert(88);
pq.insert(-45);
pq.insert(99);
int size = pq.size();
for (int i = 0; i < size; ++i) {
System.out.println(pq.delete());
}
}
}运行结果：
-45
2
2
3
5
6
88
99
124
456
678 其实相对于大顶堆的优先级队列就只将less改为了greater。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-09-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
