avatar

目录
堆和优先队列

首先我们要明白,堆实际上是一颗完全二叉树,借助完全二叉树父子节点关系的性质,我们就可以很方便的在数组中实现这一结构,而堆也分为两种,一种是大根堆,顾名思义也就是父节点value大于子节点value,小根堆则相反

动态数组

借助这个类实现堆结构,直接用ArrayList也可以


public class Array<E> {

    private E[] data;
    private int size;

    // 构造函数,传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数,默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在index索引的位置插入一个新元素e
    public void add(int index, E e){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
        if(size == data.length)
            resize(2 * data.length); //2倍扩容
        for(int i = size - 1; i >= index ; i --){
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++;
    }

    // 向所有元素后添加一个新元素
    public void addLast(E e){
        add(size, e);
    }

    // 在所有元素前添加一个新元素
    public void addFirst(E e){
        add(0, e);
    }

    // 获取index索引位置的元素
    public E get(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    // 修改index索引位置的元素为e
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

    // 查找数组中是否有元素e
    public boolean contains(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e))
                return true;
        }
        return false;
    }

    // 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
    public int find(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak
        //数据不到1/4的时候缩减
        if(size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从数组中删除元素e
    public void removeElement(E e){
        int index = find(e);
        if(index != -1)
            remove(index);
    }

    //交换
    public void swap(int a,int b){
        if (a<0||a>=size || b<0||b>=size) {
            throw new IllegalArgumentException("index illegal");
        }
        E temp=data[a];
        data[a]=data[b];
        data[b]=temp;
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for(int i = 0 ; i < size ; i ++){
            res.append(data[i]);
            if(i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }

    // 将数组空间的容量变成newCapacity大小
    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }
}

大根堆

public class MaxHeap<E extends Comparable<E>>{
    private Array<E> data;

    public MaxHeap(int capacity){
        data=new Array<>(capacity);
    }

    public MaxHeap(){
        data=new Array<>();
    }

    public int size(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    //父节点
    private int parent(int index){
        if (index==0) {
            throw new IllegalArgumentException("index 0 don't have parent");
        }
        return (index-1)/2;
    }

    //左孩子
    private int leftChild(int index){
        return index*2+1;
    }

    //右孩子
    private int rightChild(int index){
        return index*2+2;
    }

    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }

    //上浮
    private void siftUp(int cur){
        while(cur>0 && data.get(parent(cur)).compareTo(data.get(cur)) < 0){
            data.swap(cur,parent(cur));
            cur=parent(cur);
        }
    }

    public E findMax(){
        if (data.getSize()==0) {
            throw new IllegalArgumentException("heap is empty !!!");
        }
        return  data.get(0);
    }

    public E popMax(){
        if (data.getSize()==0) {
            throw new IllegalArgumentException("heap is empty !!!");
        }
        E res=findMax();
        data.swap(0,data.getSize()-1);
        data.removeLast();
        siftDown(0);
        return res;
    }    

    private void siftDown(int cur){
        while(leftChild(cur)<data.getSize()){ //有左孩子
            int large=leftChild(cur);
            //如果也有右孩子,就比较下两个节点的值取最大值
            if (large+1<data.getSize() && data.get(large).compareTo(data.get(large+1))<0) {
                large=large+1;
            }
            //比左右孩子都大就直接结束了
            if (data.get(large).compareTo(data.get(cur))<=0){
                return;
            }
            data.swap(large,cur);
            cur=large;
        }
    }
}

其实上面的实现还是有一些缺陷的,只能按照给定的键的默认排序规则进行比较,不方便实现自定义的比较规则,需要进行封装才可以,关于这一点其实可以借鉴Java中的PriorityQueue

测试

import java.util.*;
public class HeapTest{
    public static void main(String[] args) {
        int[] nums=generateRandomArray(50000000,500);
        MaxHeap heap=new MaxHeap();
        for (int i=0;i<nums.length;i++) {
            heap.add(nums[i]);
        }
        for (int i=0;i<nums.length;i++) {
            nums[i]=(int)heap.popMax();
        }
        for (int i=1;i<nums.length;i++) {
            if (nums[i-1]<nums[i]) {
                System.out.println("fuxk!!!");
                return;
            }
        }
        System.out.println("sucess!!!!!");
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }
}

PriorityQueue

package java.util;

import java.util.function.Consumer;
import sun.misc.SharedSecrets;

/**
 * An unbounded priority {@linkplain Queue queue} based on a priority heap.
 * The elements of the priority queue are ordered according to their
 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
 * provided at queue construction time, depending on which constructor is
 * used.  A priority queue does not permit {@code null} elements.
 * A priority queue relying on natural ordering also does not permit
 * insertion of non-comparable objects (doing so may result in
 * {@code ClassCastException}).
 *
 * 

The head of this queue is the least element * with respect to the specified ordering. If multiple elements are * tied for least value, the head is one of those elements -- ties are * broken arbitrarily. The queue retrieval operations {@code poll}, * {@code remove}, {@code peek}, and {@code element} access the * element at the head of the queue. * *

A priority queue is unbounded, but has an internal * capacity governing the size of an array used to store the * elements on the queue. It is always at least as large as the queue * size. As elements are added to a priority queue, its capacity * grows automatically. The details of the growth policy are not * specified. * *

This class and its iterator implement all of the * optional methods of the {@link Collection} and {@link * Iterator} interfaces. The Iterator provided in method {@link * #iterator()} is not guaranteed to traverse the elements of * the priority queue in any particular order. If you need ordered * traversal, consider using {@code Arrays.sort(pq.toArray())}. * *

Note that this implementation is not synchronized. * Multiple threads should not access a {@code PriorityQueue} * instance concurrently if any of the threads modifies the queue. * Instead, use the thread-safe {@link * java.util.concurrent.PriorityBlockingQueue} class. * *

Implementation note: this implementation provides * O(log(n)) time for the enqueuing and dequeuing methods * ({@code offer}, {@code poll}, {@code remove()} and {@code add}); * linear time for the {@code remove(Object)} and {@code contains(Object)} * methods; and constant time for the retrieval methods * ({@code peek}, {@code element}, and {@code size}). * *

This class is a member of the * * Java Collections Framework. * * @since 1.5 * @author Josh Bloch, Doug Lea * @param the type of elements held in this collection */ public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable { private static final long serialVersionUID = -7720805057305804111L; private static final int DEFAULT_INITIAL_CAPACITY = 11; /** * Priority queue represented as a balanced binary heap: the two * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The * priority queue is ordered by comparator, or by the elements' * natural ordering, if comparator is null: For each node n in the * heap and each descendant d of n, n <= d. The element with the * lowest value is in queue[0], assuming the queue is nonempty. */ transient Object[] queue; // non-private to simplify nested class access /** * The number of elements in the priority queue. */ private int size = 0; /** * The comparator, or null if priority queue uses elements' * natural ordering. * 如果没有传入比较器的话,按照元素的自然排序进行比较 */ private final Comparator<? super E> comparator; /** * The number of times this priority queue has been * structurally modified. See AbstractList for gory details. */ transient int modCount = 0; // non-private to simplify nested class access /** * Creates a {@code PriorityQueue} with the default initial * capacity (11) that orders its elements according to their * {@linkplain Comparable natural ordering}. */ public PriorityQueue() { 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; } /** * Creates a {@code PriorityQueue} containing the elements in the * specified collection. If the specified collection is an instance of * a {@link SortedSet} or is another {@code PriorityQueue}, this * priority queue will be ordered according to the same ordering. * Otherwise, this priority queue will be ordered according to the * {@linkplain Comparable natural ordering} of its elements. * 传入一个集合类型,如果是SortSet(有序)类型的集合或者也是PriorityQueue就会按照相同的规则去比较。 * 否则就会按照元素的自然排序规则去比较。 * * @param c the collection whose elements are to be placed * into this priority queue * @throws ClassCastException if elements of the specified collection * cannot be compared to one another according to the priority * queue's ordering * @throws NullPointerException if the specified collection or any * of its elements are null */ @SuppressWarnings("unchecked") public PriorityQueue(Collection<? extends E> c) { if (c instanceof SortedSet<?>) { SortedSet<? extends E> ss = (SortedSet<? extends E>) c; //拿到SortSet集合中元素的比较器,用于后序的操作 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); } } /** * Creates a {@code PriorityQueue} containing the elements in the * specified priority queue. This priority queue will be * ordered according to the same ordering as the given priority * queue. * * @param c the priority queue whose elements are to be placed * into this priority queue * @throws ClassCastException if elements of {@code c} cannot be * compared to one another according to {@code c}'s * ordering * @throws NullPointerException if the specified priority queue or any * of its elements are null */ @SuppressWarnings("unchecked") public PriorityQueue(PriorityQueue<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initFromPriorityQueue(c); } /** * Creates a {@code PriorityQueue} containing the elements in the * specified sorted set. This priority queue will be ordered * according to the same ordering as the given sorted set. * * @param c the sorted set whose elements are to be placed * into this priority queue * @throws ClassCastException if elements of the specified sorted * set cannot be compared to one another according to the * sorted set's ordering * @throws NullPointerException if the specified sorted set or any * of its elements are null */ @SuppressWarnings("unchecked") 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); } } //从SortSet有序集合中的元素直接复制到当前的queue中 private void initElementsFromCollection(Collection<? extends E> c) { Object[] a = c.toArray(); // If c.toArray incorrectly doesn't return Object[], copy it. 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; } /** * Initializes queue array with elements from the given Collection. * 从无序集合中构建queue * @param c the collection */ private void initFromCollection(Collection<? extends E> c) { initElementsFromCollection(c); //复制完成之后进行调整 heapify(); } /** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * Increases the capacity of the array. * queue 数组扩容 * @param minCapacity the desired minimum capacity */ 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) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } /** * Inserts the specified element into this priority queue. * * @return {@code true} (as specified by {@link Collection#add}) * @throws ClassCastException if the specified element cannot be * compared with elements currently in this priority queue * according to the priority queue's ordering * @throws NullPointerException if the specified element is null */ public boolean add(E e) { return offer(e); } /** * Inserts the specified element into this priority queue. * * @return {@code true} (as specified by {@link Queue#offer}) * @throws ClassCastException if the specified element cannot be * compared with elements currently in this priority queue * according to the priority queue's ordering * @throws NullPointerException if the specified element is null */ 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; } public E peek() { return (size == 0) ? null : (E) queue[0]; } private int indexOf(Object o) { if (o != null) { for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; } return -1; } /** * Removes a single instance of the specified element from this queue, * if it is present. More formally, removes an element {@code e} such * that {@code o.equals(e)}, if this queue contains one or more such * elements. Returns {@code true} if and only if this queue contained * the specified element (or equivalently, if this queue changed as a * result of the call). * * @param o element to be removed from this queue, if present * @return {@code true} if this queue changed as a result of the call */ public boolean remove(Object o) { int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } } /** * Version of remove using reference equality, not equals. * Needed by iterator.remove. * * @param o element to be removed from this queue, if present * @return {@code true} if removed */ boolean removeEq(Object o) { for (int i = 0; i < size; i++) { if (o == queue[i]) { removeAt(i); return true; } } return false; } public boolean contains(Object o) { return indexOf(o) != -1; } public Object[] toArray() { return Arrays.copyOf(queue, size); } public <T> T[] toArray(T[] a) { final int size = this.size; if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(queue, size, a.getClass()); System.arraycopy(queue, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } public Iterator<E> iterator() { return new Itr(); } private final class Itr implements Iterator<E> { /** * Index (into queue array) of element to be returned by * subsequent call to next. */ private int cursor = 0; /** * Index of element returned by most recent call to next, * unless that element came from the forgetMeNot list. * Set to -1 if element is deleted by a call to remove. */ private int lastRet = -1; private ArrayDeque<E> forgetMeNot = null; /** * Element returned by the most recent call to next iff that * element was drawn from the forgetMeNot list. */ private E lastRetElt = null; /** * The modCount value that the iterator believes that the backing * Queue should have. If this expectation is violated, the iterator * has detected concurrent modification. */ private int expectedModCount = modCount; public boolean hasNext() { return cursor < size || (forgetMeNot != null && !forgetMeNot.isEmpty()); } @SuppressWarnings("unchecked") public E next() { if (expectedModCount != modCount) throw new ConcurrentModificationException(); if (cursor < size) return (E) queue[lastRet = cursor++]; if (forgetMeNot != null) { lastRet = -1; lastRetElt = forgetMeNot.poll(); if (lastRetElt != null) return lastRetElt; } throw new NoSuchElementException(); } public void remove() { if (expectedModCount != modCount) throw new ConcurrentModificationException(); if (lastRet != -1) { E moved = PriorityQueue.this.removeAt(lastRet); lastRet = -1; if (moved == null) cursor--; else { if (forgetMeNot == null) forgetMeNot = new ArrayDeque<>(); forgetMeNot.add(moved); } } else if (lastRetElt != null) { PriorityQueue.this.removeEq(lastRetElt); lastRetElt = null; } else { throw new IllegalStateException(); } expectedModCount = modCount; } } public int size() { return size; } public void clear() { modCount++; for (int i = 0; i < size; i++) queue[i] = null; size = 0; } @SuppressWarnings("unchecked") 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; } /** * Removes the ith element from queue. * 删除某个位置的元素 * Normally this method leaves the elements at up to i-1, * inclusive, untouched. Under these circumstances, it returns * null. Occasionally, in order to maintain the heap invariant, * it must swap a later element of the list with one earlier than * i. Under these circumstances, this method returns the element * that was previously at the end of the list and is now at some * position before i. This fact is used by iterator.remove so as to * avoid missing traversing elements. */ private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element 移除最后一个元素 queue[i] = null; else { E moved = (E) queue[s]; //保存队列尾部的元素 queue[s] = null; //置为null siftDown(i, moved); //moved直接插入到i位置,相当于直接删除了i位置的元素 if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; } /** * Inserts item x at position k, maintaining heap invariant by * promoting x up the tree until it is greater than or equal to * its parent, or is the root. * 将x插入k位置,并进行上浮调整 * To simplify and speed up coercions and comparisons. the * Comparable and Comparator versions are separated into different * methods that are otherwise identical. (Similarly for siftDown.) * * @param k the position to fill * @param x the item to insert */ private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } @SuppressWarnings("unchecked") 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; } @SuppressWarnings("unchecked") 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; } /** * Inserts item x at position k, maintaining heap invariant by * demoting x down the tree repeatedly until it is less than or * equal to its children or is a leaf. * 插入元素x到到位置k,并进行下沉调整 * * @param k the position to fill * @param x the item to insert */ private void siftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); //带比较器的 else siftDownComparable(k, x); //不带比较器,用x的compator } @SuppressWarnings("unchecked") 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; } @SuppressWarnings("unchecked") 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; } /** * Establishes the heap invariant (described above) in the entire tree, * assuming nothing about the order of the elements prior to the call. */ @SuppressWarnings("unchecked") private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); } public Comparator<? super E> comparator() { return comparator; } /** * Saves this queue to a stream (that is, serializes it). * * @serialData The length of the array backing the instance is * emitted (int), followed by all of its elements * (each an {@code Object}) in the proper order. * @param s the stream */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out element count, and any hidden stuff s.defaultWriteObject(); // Write out array length, for compatibility with 1.5 version s.writeInt(Math.max(2, size + 1)); // Write out all elements in the "proper order". for (int i = 0; i < size; i++) s.writeObject(queue[i]); } /** * Reconstitutes the {@code PriorityQueue} instance from a stream * (that is, deserializes it). * * @param s the stream */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in size, and any hidden stuff s.defaultReadObject(); // Read in (and discard) array length s.readInt(); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, size); queue = new Object[size]; // Read in all elements. for (int i = 0; i < size; i++) queue[i] = s.readObject(); // Elements are guaranteed to be in "proper order", but the // spec has never explained what that might be. heapify(); } /** * Creates a late-binding * and fail-fast {@link Spliterator} over the elements in this * queue. * *

The {@code Spliterator} reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}. * Overriding implementations should document the reporting of additional * characteristic values. * * @return a {@code Spliterator} over the elements in this queue * @since 1.8 */ public final Spliterator<E> spliterator() { return new PriorityQueueSpliterator<E>(this, 0, -1, 0); } static final class PriorityQueueSpliterator<E> implements Spliterator<E> { /* * This is very similar to ArrayList Spliterator, except for * extra null checks. */ private final PriorityQueue<E> pq; private int index; // current index, modified on advance/split private int fence; // -1 until first use private int expectedModCount; // initialized when fence set /** Creates new spliterator covering the given range */ PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence, int expectedModCount) { this.pq = pq; this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; } private int getFence() { // initialize fence to size on first use int hi; if ((hi = fence) < 0) { expectedModCount = pq.modCount; hi = fence = pq.size; } return hi; } public PriorityQueueSpliterator<E> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : new PriorityQueueSpliterator<E>(pq, lo, index = mid, expectedModCount); } @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> action) { int i, hi, mc; // hoist accesses and checks from loop PriorityQueue<E> q; Object[] a; if (action == null) throw new NullPointerException(); if ((q = pq) != null && (a = q.queue) != null) { if ((hi = fence) < 0) { mc = q.modCount; hi = q.size; } else mc = expectedModCount; if ((i = index) >= 0 && (index = hi) <= a.length) { for (E e;; ++i) { if (i < hi) { if ((e = (E) a[i]) == null) // must be CME break; action.accept(e); } else if (q.modCount != mc) break; else return; } } } throw new ConcurrentModificationException(); } public boolean tryAdvance(Consumer<? super E> action) { if (action == null) throw new NullPointerException(); int hi = getFence(), lo = index; if (lo >= 0 && lo < hi) { index = lo + 1; @SuppressWarnings("unchecked") E e = (E)pq.queue[lo]; if (e == null) throw new ConcurrentModificationException(); action.accept(e); if (pq.modCount != expectedModCount) throw new ConcurrentModificationException(); return true; } return false; } public long estimateSize() { return (long) (getFence() - index); } public int characteristics() { return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; } } }

扩展

d叉堆:多叉堆,上面我们实现的都是二叉堆,但是其实我们还可以将其扩展为多叉堆,一个节点有多个子节点

索引堆:我们上面实现的二叉堆只能看见堆顶的元素,看不到堆中的元素,有时候我们可能需要操作堆中间的元素,索引堆顾名思义就是有索引可以对应每个元素,借此就可以操作堆中间的元素

二项堆斐波拉契堆 ….. 这些结构其实都是扩展的,简单了解即可

源码地址

Github

文章作者: imlgw
文章链接: http://imlgw.top/2019/12/01/dui-he-you-xian-dui-lie/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 iMlGw0
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论