【数据结构】Java 常用集合类 PriorityQueue

关注
发布于: 2020 年 07 月 22 日
PriorityQueue 整体设计PriorityQueue 继承自抽象父类 AbstractQueue 的优先级队列，使用小顶堆实现每次取出的元素都是队列中权值最小的。元素大小的判断可以通过传入的比较器计算，否则采用自然排序。不允许放入 null。
﻿
按照堆的特点可以把堆分为大顶堆和*小顶堆*
大顶堆：每个结点的值都大于或*等于*其左右孩子结点的值
小顶堆：每个结点的值都小于或*等于*其左右孩子结点的值
﻿
public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable { 
}
PriorityQueue 属性和构造函数主要属性
// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 表示为平衡二叉堆的优先级队列：queue[n]的两个子节点列是queue[2*n+1]和queue[2*(n+1)]
transient Object[] queue; 
// 队列元素数量
private int size = 0;
// 比较器，用于定义比较规则
private final Comparator<? super E> comparator;
﻿
构造函数
// 默认构造器
public PriorityQueue() {
  	this(DEFAULT_INITIAL_CAPACITY, null);
}
// 指定初始容量
public PriorityQueue(int initialCapacity) {
  	this(initialCapacity, null);
}
// 对初始容量的要求 >= 1
public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
  	if (initialCapacity < 1)
  	  	throw new IllegalArgumentException();
  	this.queue = new Object[initialCapacity];
  	this.comparator = comparator;
}
// 对 SortedSet 和 PriorityQueue 特殊处理
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}
﻿
使用 SortedSet 初始化，已经是排序数组，直接赋值
private void initElementsFromCollection(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if (a.getClass() != Object[].class)
        a = Arrays.copyOf(a, a.length, Object[].class);
    int len = a.length;
    // 不支持有 null 元素
    if (len == 1 || this.comparator != null)
  	  	for (int i = 0; i < len; i++)
  	  	  	if (a[i] == null)
  	  	  	  	throw new NullPointerException();
  	this.queue = a;
  	this.size = a.length;
}
﻿
使用 PriorityQueue 初始化，直接赋值
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
    if (c.getClass() == PriorityQueue.class) {
        this.queue = c.toArray();
        this.size = c.size();
    } else {
        initFromCollection(c);
    }
}
﻿
使用其他集合类初始化，调用 heapify() 调整顺序
private void initFromCollection(Collection<? extends E> c) {
  	initElementsFromCollection(c);
  	heapify();
}
添加元素可以调用 add() 或 offer() 添加元素
public boolean add(E e) {
  	return offer(e);
}
public boolean offer(E e) {
  	if (e == null)
    		throw new NullPointerException();
  	modCount++;
  	int i = size;
  	if (i >= queue.length)
  	  	// 扩容
  	  	grow(i + 1);
  	size = i + 1;
  	if (i == 0)
  	  	queue[0] = e;
  	else
  	  	// 加入元素，和上层元素进行调整
  	  	siftUp(i, e);
  	return true;
}
向上调整元素不断地和 parent（queue[(k-1)/2]）比较，如果小于 parent 进行互换
// k 当前位置，x 当前元素，向上调整
private void siftUp(int k, E x) {
  	// 选择比较器
  	if (comparator != null)
      	siftUpUsingComparator(k, x);
  	else
      	siftUpComparable(k, x);
}
// 默认比较器
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
  	  	// 找到 parent，如果小于 parent，进行换位
  	  	int parent = (k - 1) >>> 1;
  	  	Object e = queue[parent];
  	  	if (key.compareTo((E) e) >= 0)
  	  	  	break;
  	  	queue[k] = e;
  	  	k = parent;
  	}
  	queue[k] = key;
}
// 使用指定比较器
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
  	  	int parent = (k - 1) >>> 1;
  	  	Object e = queue[parent];
  	  	if (comparator.compare(x, (E) e) >= 0)
  	  	  	break;
  	  	queue[k] = e;
  	  	k = parent;
  	}
    queue[k] = x;
}
扩容 grow如果 queue 数组已经占满，进行扩容，扩容后大小计算以 64 为分界线，并且如果 newCapacity 增加到 MAXARRAYSIZE，调用 hugeCapacity() 计算的到。扩容是通过数组拷贝的方式。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
  	  	newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    return (minCapacity > MAX_ARRAY_SIZE) ?
  	    Integer.MAX_VALUE :
	  	  MAX_ARRAY_SIZE;
}
取出元素peek() 方法返回堆顶元素，poll() 方法返回并移除堆顶元素
public E peek() {
	  return (size == 0) ? null : (E) queue[0];
}
public E poll() {
    if (size == 0)
      	return null;
    int s = --size;
    modCount++;
  	// 堆顶元素返回并移除
    E result = (E) queue[0];
  	// 取出最后一个元素放到堆顶位置，向下调整
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
	      siftDown(0, x);
    return result;
}
向下调整元素
private void siftDown(int k, E x) {
    if (comparator != null)
  	  	siftDownUsingComparator(k, x);
    else
  	  	siftDownComparable(k, x);
}
// child默认为小的那个下标，记录小的对象为c；，就结束循环，调整完成，否则将c赋值为queue[k]，k = child，继续向下调整。
    
private void siftDownUsingComparator(int k, E x) {
  	// 最后一层非叶子节点层
    int half = size >>> 1;
    while (k < half) {
      	// k的左子节点child，右子节点right
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
      	// 如果右子节点存在，找到比较小的子节点，作为c取出，下标为child
        if (right < size &&
          	  comparator.compare((E) c, (E) queue[right]) > 0)
	          c = queue[child = right];
      	// 如果x大于c，进行交换，并进入下一层循环
        if (comparator.compare(x, (E) c) <= 0)
  	        break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            	((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
          	c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
	          break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}
删除元素默认删除堆顶元素，如果删除指定元素先找到元素位置，然后移除
public E remove() {
    E x = poll();
    if (x != null)
      return x;
    else
      throw new NoSuchElementException();
}
// 先找到元素位置
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
	      return false;
    else {
  	    removeAt(i);
    	  return true;
    }
}
// 如果移除的是叶子节点，直接置为 null
private E removeAt(int i) {
    modCount++;
    int s = --size;
    if (s == i)
      queue[i] = null;
    else {
      E moved = (E) queue[s];
      queue[s] = null;
      // 移除节点向下调整，逻辑同取出元素后的操作
      siftDown(i, moved);
      if (queue[i] == moved) {
        siftUp(i, moved);
        if (queue[i] != moved)
          return moved;
      }
    }
    return null;
}
heapify 方法
private void heapify() {
  	// 从 queue[size/2-1] 位置开始执行 siftDown
  	// 即最后一层非叶子节点开始调整位置
  	for (int i = (size >>> 1) - 1; i >= 0; i--)
  	  	siftDown(i, (E) queue[i]);
}
iterator 方法优先级队列的迭代器
public Iterator<E> iterator() {
  	return new Itr();
}
private final class Itr implements Iterator<E> {
  	// next 元素的坐标
  	private int cursor = 0;
  	// 移除元素存入
  	private ArrayDeque<E> forgetMeNot = null;
  
  	// 最近一次获取的元素的坐标，如果元素已经被 remove 则为 -1
  	private int lastRet = -1;
  	// 最近一次从 forgetMeNot 出队列的元素
  	private E lastRetElt = null;
  	public boolean hasNext() {
  	  	return cursor < size ||
  	  	  	(forgetMeNot != null && !forgetMeNot.isEmpty());
  	}
  	// 先从 queue 中依次获取
  	public E next() {
  	  	if (cursor < size)
  	  	  	return (E) queue[lastRet = cursor++];
  	  	if (forgetMeNot != null) {
  	  	  	lastRet = -1;
  	  	  	// 从 forgetMeNot 队列中出队列
  	  	  	lastRetElt = forgetMeNot.poll();
  	  	  	if (lastRetElt != null)
  	  	  	  	return lastRetElt;
  	  	}
  	  	throw new NoSuchElementException();
  	}
  	public void remove() {
  	  	if (lastRet != -1) {
  	  	  	// 移除 lastRet
  	  	  	E moved = PriorityQueue.this.removeAt(lastRet);
  	  	  	lastRet = -1;
  	  	  	if (moved == null)
  	  	  	  	cursor--;
  	  	  	else {
  	  	  	  	if (forgetMeNot == null)
  	  	  	  	  	forgetMeNot = new ArrayDeque<>();
  	  	  	  	// 放入 forgetMeNot 队列
  	  	  	  	forgetMeNot.add(moved);
  	  	  	}
  	  	} else if (lastRetElt != null) {
  	  	  	PriorityQueue.this.removeEq(lastRetElt);
  	  	  	lastRetElt = null;
  	    } else {
  	  	  	throw new IllegalStateException();
  	  	}
  	}
}
﻿
﻿
发布于: 2020 年 07 月 22 日阅读数: 60
原文链接:【http://xie.infoq.cn/article/2e88b947fe14d35d94305fd38】。
Alex🐒

关注
还未添加个人签名 2020.04.30 加入
还未添加个人简介
发布
暂无评论
创作场景

【数据结构】Java 常用集合类 PriorityQueue

PriorityQueue 整体设计

PriorityQueue 属性和构造函数

添加元素

向上调整元素

扩容 grow

取出元素

向下调整元素

删除元素

heapify 方法

iterator 方法

Alex🐒

评论
