catalogue
Return queue header element / out of queue operation
Analysis of bottom binary heap algorithm
Talk about the heap sorting algorithm
Member variable
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;
/**
The priority queue is represented as a balanced binary heap (complete binary tree): the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is sorted by the natural order of the comparator or elements. If the comparator is empty: 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 that the queue is not empty.
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* Number of elements in the priority queue.
*/
private int size = 0;
/**
Comparator, null if the priority queue uses the natural order of elements.
*/
private final Comparator<? super E> comparator;
/**
The number of times this priority queue has been structurally modified. For more information, see AbstractList.
*/
transient int modCount = 0; // non-private to simplify nested class access
......
}Here, we should pay attention to the array queue. Although its bottom layer is an array, because it involves the order problem, the logic bottom layer adopts the binary heap structure and considers the array queue as a complete binary tree. That is, if a node is queue[i], its left child is queue[2*i+1], and its right child is queue[2*i+2], where comparator is the key to sorting. If it is null, it is sorted naturally, otherwise it is sorted according to the definition of this comparator.
Constructor
/**
Create a PriorityQueue with a default initial capacity (11), which sorts the elements according to their natural order.
*/
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
Create a PriorityQueue with the specified initial capacity and sort the elements according to their natural order.
Parameters:
initialCapacity – Initial capacity of this priority queue
Throw:
IllegalArgumentException – If initialCapacity is less than 1
*/
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
Create a PriorityQueue with default initial capacity, and its elements are sorted according to the specified comparator.
Parameters:
Comparator – the comparator that will be used to sort this priority queue. If null, the natural order of the elements is used.
since:
1.8
*/
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
Create a PriorityQueue with the specified initial capacity and sort its elements according to the specified comparator.
Parameters:
initialCapacity – Initial capacity of this priority queue
Comparator – the comparator that will be used to sort this priority queue. If null, the natural order of the elements is used.
Throw:
IllegalArgumentException – If initialCapacity is less than 1
*/
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 PriorityQueue containing the elements in the specified collection. If the specified set is an instance of SortedSet or another PriorityQueue, the priority queue will be sorted in the same order. Otherwise, this priority queue is sorted according to the natural order of its elements.
Parameters:
c - The collection whose elements will be placed in this priority queue
Throw:
ClassCastException – If the {elements of the specified set cannot be compared with each other according to the order of the priority queue
NullPointerException – If the specified collection or any of its elements is empty
*/
@SuppressWarnings("unchecked")
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);
}
}
/**
Creates a PriorityQueue that contains the elements in the specified priority queue. The priority queue will be sorted in the same order as the given priority queue.
Parameters:
c - The priority queue whose elements will be placed in the priority queue
Throw:
ClassCastException -If element c cannot be compared with another basis, order with one c
NullPointerException – If the specified priority queue or any of its elements is empty
*/
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
/**
Creates a PriorityQueue containing the elements in the specified sort set. This priority queue will be sorted in the same order as the given sort set.
Parameters:
c – Elements will be placed in an ordered collection of this priority queue
Throw:
ClassCastException – If the elements of the specified sort set cannot be compared with each other according to the order of the sort set
NullPointerException – If the specified ordered collection or any of its elements is empty
*/
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}Here we mainly explain that the following formal parameters are Collection related constructors: first, we will judge whether they are SortedSet or PriorityQueue types, which will be simpler:
private void initElementsFromCollection(Collection<? extends E> c) { //Copy directly
Object[] a = c.toArray();
if (c.getClass() != ArrayList.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;
}
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) { //PriorityQueue is also copied directly
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}If not, it will be different. There is a heap sorting process.
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify(); //Adjustment reactor
}
/**
Establish heap invariants throughout the tree (as described above) without assuming the order of elements before calling.
*/
@SuppressWarnings("unchecked")
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--) //Sink nodes from all nodes that are not leaf nodes
siftDown(i, (E) queue[i]);
}
add to
public boolean add(E e) {
return offer(e);
}
/**
Inserts the specified element into this priority queue.
return:
true (By queue Offer (specify)
Throw:
ClassCastException – If the specified element cannot be compared with the element currently in this priority queue according to the order of the priority queue
NullPointerException – If the specified element is empty
*/
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) //If empty, the first
queue[0] = e;
else
siftUp(i, e); //After inserting the end, the heap node floats up
return true;
}
/**
Increase the capacity of the array.
Parameters:
minCapacity – Minimum capacity required
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Capacity expansion strategy
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);
}This involves the floating up operation of the node after adding elements to the tail, which will be described in detail later.
Return queue header element / out of queue operation
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
/**
Retrieves but does not delete the header of this queue. This method differs from peek only in that it throws an exception if the queue is empty.
Unless the queue is empty, this implementation will return the result of peek.
return:
The head of this queue
Throw:
NoSuchElementException – If this queue is empty
*/
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
//The first node exchanges with the end node, and then sets null at the end to sink the first node.
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);//Sinking of head node
return result;
}delete
/*
Removes a single instance, if any, of the specified element from this queue. More formally, if the queue contains one or more such elements, delete element e so that o.equals(e). Returns true if and only if the queue contains the specified element (or, equivalently, if the queue changes due to a call).
Parameters:
o - The element (if any) to remove from this queue
return:
true if this queue changes due to a call
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
private int indexOf(Object o) { //Returns the first matching index
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
/**
Removes the ith element from the queue. Typically, this method retains up to I-1 (including i-1) elements and is not affected. In these cases, it returns null. Sometimes, in order to keep the heap unchanged, it must swap the later elements in the list with elements earlier than I. In these cases, this method returns the element that was at the end of the list and is now somewhere before I. This fact is used by the iterator Remove is used to avoid losing traversal elements.
*/
@SuppressWarnings("unchecked")
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;//The last element is directly set to null to facilitate gc
else {//Middle position
E moved = (E) queue[s]; //Swap with the last location element and set the last location to null
queue[s] = null;
siftDown(i, moved);//Then sink first
if (queue[i] == moved) {
siftUp(i, moved);//Float up again
if (queue[i] != moved)
return moved;
}
}
return null;
}Analysis of bottom binary heap algorithm
The core of the data structure is the implementation of binary small top heap (the parent node is less than two child nodes). The insertion and deletion of data will lead to the change of binary heap structure.
Floating of heap nodes
/**
Insert item x at position k and keep the heap unchanged by lifting x up the tree until it is greater than or equal to its parent or root. Simplify and accelerate forcing and comparison. The Comparable and Comparator versions are divided into different methods, which are otherwise the same. (similar to siftDown.)
Parameters:
k - Position to fill
x - Items to insert
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x); //Natural sorting
}
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1; //Parent node
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0) //If the node is larger than the parent node, there is no need to float up
break;
//Swap, and then continue to consider whether the node needs to float up
queue[k] = e;
k = parent;
}
queue[k] = x;//assignment
}That is, each time a node is placed from the middle or tail, it needs to compare with its parent node whether it is smaller than the parent node. If it is smaller, it needs to float up until it is equal to or larger than the parent node. This is necessary to ensure a minimum heap.
Sinking of reactor node
/**
Insert the item x at position k and keep the heap unchanged by repeatedly demoting x to the tree until it is less than or equal to its children or leaves.
Parameters:
k - Position to fill
x - Items to insert
*/
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; //
while (k < half) {//Make sure there are child node comparisons
int child = (k << 1) + 1; // If there is a child node, there must be a left child node
Object c = queue[child];
int right = child + 1;
if (right < size &&//If the right child node exists, select the smaller of the two
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0) //If the node is smaller than the smaller one inside, there is no need to sink
break;
//Otherwise, switch nodes.
queue[k] = c;
k = child;
}
queue[k] = key;//assignment
}Each time a node is inserted from the head or middle, it needs to be compared whether it is larger than its child node. If so, it needs to sink. This is necessary to ensure a minimum heap.
summary
-
Each time an element is added from the end of the array, the element may not be the largest and needs to float up to the appropriate position.
-
Each time a queue element is popped, the first element needs to be popped. The method is to exchange with the last element first, and then set the last element to null. In this way, the current first element may not be the smallest, so it needs to sink to the appropriate position.
-
Every time the element is deleted, the node is exchanged with the end node, and then the node is sunk / floated to ensure the structure of the small top pile.
Talk about the heap sorting algorithm
Heap sorting algorithm can actually start with small top heap or large top heap. The small top heap is sorted from front to back, and the large top heap is sorted from back to front.
Here is the idea of large top reactor:
The essence of the heap sorting algorithm is to wipe the first 0~n-i nodes in each I round:
Find the maximum value for n-i nodes in each round:
Start with the first n-i non leaf nodes and see their relationship with the size of child nodes. If the child node is larger than the parent node, the child node needs to float up.
In this way, we can finally find the maximum node value of the round and put it on the top of the heap, which is a formal parameter of the big top heap. Swap this value with the end node.
Code Demo:
public class HeapSort {
/**
*
* @param list Sorted list
* @param k Investigate the location of nodes
* @param n Furthest index to consider
*/
public static void heapAdjust(ArrayList<? extends Comparable> list,int k,int n){
while(2*k+1<=n-1){
int i=2*k+1;
if(i<=n-2&&list.get(i+1).compareTo(list.get(i))>0){
i+=1;//right child
}
if(list.get(i).compareTo(list.get(k))>0){ //The child node is larger than the parent node
Collections.swap(list,k,i);
k=i; //continue
}else{
break;
}
}
}
/**
*
* @param list Sort list
*/
public static void HeapSort(ArrayList<? extends Comparable> list){
int n=list.size();
//Adjust to large top pile
for(int i=n/2-1;i>=0;i--){
heapAdjust(list,i,n);
}
//sort
for(int i=n-1;i>0;i--){
Collections.swap(list,i,0);
heapAdjust(list,0,i);
}
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
Random random = new Random(47);
for (int i = 0; i < 10; i++) {
list.add(random.nextInt(20));
}
System.out.println(list); //Before sorting
HeapSort(list);
System.out.println(list);//After sorting
}
}