欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先队列java-PriorityQueue

程序员文章站 2024-02-14 23:59:28
...

PriorityQueue,也就是优先队列,所谓的优先队列,就是在队列中根据某一个特征值自动进行排序,优先队列分为两种,最大优先队列和最小优先队列,优先队列的一个最大特性就是,当插入元素或者删除元素的时候,队列会自动进行调整,保证队首元素一定是优先权最大/最小。正是由于优先队列的这种特性,优先队列可以被用在很多地方,比如作业调度,进程调度等。

优先队列java-PriorityQueue

优先队列java-PriorityQueue

堆与堆排序

优先队列的内部是采用堆这一种数据结构来实现的,并且,在进行操行的时候,时刻进行堆的维护。

比较常用的一种堆结构是二叉堆,二叉堆的实质是一个二叉树,只不过这个二叉树有点特殊,每一个父子节点都是其子孙节点中的最大值,称之为最大堆,反之则称之为最小堆,下面采用最大堆来演示,最小堆原理相同,二叉堆一般采用数组来进行维护即可,并且,由于其本身的特性,可以得出结论,堆的左孩子索引为 i * 2+1, 右孩子索引为 i * 2 + 2,其中i为父亲节点的索引

从图中可以看到,每一个父子节点的值都比其子孙节点大,也就是说,根节点的值是整个堆中的值最大的一个,这就是最大
堆名字的由来了

建立二叉堆的方法非常简单,根据二叉堆的特性,只需要对每个元素执行调整即可,调整的具体过程为,从后往前调整,如果发现一个元素的值比其孩子节点(左右孩子)的值小,则跟其进行交换,并且递归其发生交换的孩子,继续进行判断,交换,直至到达第一个元素,不过这里有一个可以提高效率的地方,从元素个数/2-1开始即可

二叉堆排序是根据堆的这种特性而出现的一种排序算法,算法的流程为,首先建立二叉堆,然后每次交换第一个元素(也就是当前的最大值)与最后一个元素,调整堆,将堆的大小-1,重复上面的操作,直至堆大小为1,具体代码如下:




优先队列(PriorityQueue)源码剖析

首先是构造方法


    // 无参构造器,默认大小为11
    public PriorityQueue() {
        // DEFAULT_INITIAL_CAPACITY = 11;
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    // 指定大小的构造器
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    // 提供一个比较器构造器
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

    // 指定容量并且提供一个比较器的构造器
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    // 使用容器中的数据来构造优先队列
    // 其中的SortedSet将在后面学习
    // 从这里可以看到,如果建立的元素已经是有序的,也就是已经提供了比较器,则直接使用
    // 如果不是,则按照默认的方式进行堆的建立
    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);
        }
    }

    // 使用另一个优先队列来构造
    public PriorityQueue(PriorityQueue<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }

    // 使用SortedSet来构造
    public PriorityQueue(SortedSet<? extends E> c) {
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }

    // 从优先队列构造
    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
        if (c.getClass() == PriorityQueue.class) {
            this.queue = c.toArray();
            this.size = c.size();
        } else {
            initFromCollection(c);
        }
    }

    // 从容器中构造,并且建立堆
    private void initFromCollection(Collection<? extends E> c) {
        initElementsFromCollection(c);
        heapify();
    }

    // 从容器中构造
    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;
        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;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

堆的建立与调整


    // 建立堆
    private void heapify() {
        // 从非叶子节点进行调整
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

    // 如果提供了比较器,则使用比较器进行堆调整
    // 否则,使用默认的比较器进行堆调整
    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

    // 使用比较器进行堆调整,可以看到,实现方式跟上面的调整方式基本一样
    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        // 从上往下开始调整
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            // 这里需要注意的是,默认建立的是最小堆
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

    // 如果没有提供比较器,则使用元素默认的构造器
    // 这也就意味着传入的元素必须是实现了Comparable接口
    // 并且已经实现compareTo方法
    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;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

插入元素

public class Heap {
	private int[] data;
	private int heapSize;

	public Heap(int[] data, int heapSize) {
		this.data = data;
		this.heapSize = heapSize;
	}

	// 建立二叉堆
	private void buildHeap() {
		// 从索引为堆大小/2 - 1 开始,调整元素的位置
		for (int i = (heapSize >>> 1) - 1; i >= 0; i--) {
			heap(i);
		}
	}

	// 建立二叉堆的具体实现
	private void heap(int i) {
		int left = (i << 1) + 1; // 左孩子索引(2*n + 1)
		int right = left + 1; // 右孩子索引(2*n + 2)
		int max = i;
		// 如果左孩子的值比父亲的值大,则记录下左孩子索引
		if (left < heapSize && data[left] > data[i]) {
			max = left;
		}
		// 如果右孩子的值比当前的最大值大,则记录下其索引
		if (right < heapSize && data[right] > data[max]) {
			max = right;
		}
		// 如果孩子的值比父亲大,则进行交换
		// 否则,则结束,表明已经是最大堆了
		if (max != i) {
			int tmp = data[i];
			data[i] = data[max];
			data[max] = tmp;
			// 递归发生交换的孩子节点
			heap(max);
		}
	}
	
	 // 堆排序
    public void sort(){
        // 建立堆
        buildHeap();
        while (heapSize >= 2){
            // 将第一个元素与最后一个元素交换
            int tmp = data[heapSize - 1];
            data[heapSize - 1] = data[0];
            data[0] = tmp;
            // 堆大小-1
            heapSize --;
            // 从根节点调整堆,使其重新成为最大堆
            heap(0);
        }
    }
	
    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;
    }

    // 动态增长
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // 如果容量小于64,则增长一倍,否则,增长1/2
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // 检查是否整数溢出
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

    // 检查是否溢出
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

    // 根据有无提供比较器选择不同的比较方法
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

    // 从这里可以看到,调整的方法为从位置k开始,查找其
    // 父节点的值,如果父节点的值比所要插入的值大,则进行交换,并且递归父节点
    // 也就是从二叉树树中"往上调整"
    // 否则,则不进行交换(最小堆嘛)
    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;
    }

    // 同上,只是这里使用默认的比较器
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83

获得元素的索引


    private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

删除元素


    public boolean remove(Object o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }
    // 如果有相等的元素,则删除
    boolean removeEq(Object o) {
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

    // 删除指定位置的元素
    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;
    }

    // 删除元素,默认为第一个元素,也就是根元素
    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;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

优先队列的本质其实就是一个最小堆,如果要使用最大优先队列,则需要传入自定义的比较器,在优先队列中,不需要存在空元素,并且要求传入优先队列中的元素必须是实现了Comparable接口