Priority queues and heaps

What is a priority queue?

As you can see from the name, a priority queue is also a queue, except that the queue exits in order of priority. In some cases, it may be necessary to find the smallest or largest element in the set of elements. This can be done using a priority queue ADT (Abstract Data Type), which is a Data structure, It supports insert and delete minimum (return and delete minimum element) or delete maximum (return and delete maximum element);

These operations are equivalent to the enQueue and deQueue operations of queues, except that for priority queues, the order in which elements are queued may be different from the order in which they are operated. Job scheduling is an application instance of priority queues, which schedules elements according to their priorities rather than on a first-come, first-served basis.

If the smallest key element has the highest priority, this queue is called an ascending priority queue (that is, the smallest element is always deleted first). Similarly, if the largest key element has the highest priority, this queue is called a descending priority queue (that is, the largest element is always deleted first). Because these two types are symmetric, you only need to pay attention to one of them, such as the ascending priority queue.

Priority queue operation

The following operations form an ADT of the priority queue;

Priority queues are containers of elements, each of which has an associated key;

• insert(key, data): Inserts the key data into the priority queue. The elements are sorted by their key.
• deleteMin/deleteMax: Removes and returns the element with the minimum/maximum key;
• getMinimum/getMaximum: Returns the element of the smallest/largest finger, but does not delete it;

2. Auxiliary operations on priority queues

• The KTH is minimum/the KTH is maximum: Returns the KTH smallest/largest element in the priority queue.
• Size (size): Returns the number of elements in the priority queue.
• Heap Sort: Sorts the elements in the priority queue based on the priority of the key value;

Priority queue application

• Data compression: Huffman coding algorithm;
• Shortest path algorithm: Dijkstra algorithm;
• Minimum spanning tree algorithm: Prim algorithm;
• Event-driven simulation: Customer queuing algorithm;
• Selection problem: find the KTH smallest element;
• Wait, wait, wait….

Implementation comparison of priority queues

Heap implementation is not limited to a particular way, can be implemented using a chained tree structure (nodes have left and right Pointers), can also be implemented using an array, because the properties of a complete binary tree are arranged layer by layer in order and can be neatly placed in an array. And array based heap implementation is a more clever and efficient way, is the most common way.

Heap and binary heap

What is a heap?

A heap is a binary tree with specific properties. The basic requirement of a heap is that the value of all nodes in the heap must be greater than or equal to (or less than or equal to) the value of its child nodes, which is also called the property of the heap. Another property of the heap is that when h > 0, all leaf nodes are in the h or H-1 layer (where H is the height of the tree, a complete binary tree). In other words, the heap should be a complete binary tree.

In the following example, the tree on the left is a heap (each element is greater than its child), while the tree on the right is not a heap (because 5 is greater than its child 2)

Binary heap

In binary heap, each node has at most two children nodes. In practical application, binary heap is enough to meet the needs, so the next chapter mainly discusses binary minimum heap and binary maximum heap.

One possible way to do this is to use arrays. Since the heap is formally a complete binary tree, storing it in arrays does not waste any space, as shown in the following figure:

Using arrays to represent heaps not only wastes space but also has certain advantages:

• The left child of each node is twice the subscript I:left child(i) = i * 2; The right child of each node is 2 times the subscript I plus 1:right child(i) = i * 2 + 1
• The parent of each node is one half of the subscript:parent(i) = i / 2Notice that this is integer division, 2 and 3 divided by 2 are both 1, and you can verify that;
• ** note: ** here is the space where the subscript 0 is empty, mainly for easy to understand, if 0 is not empty, just need to calculate the value of I to the right of one position (that is, increment 1, you can try, the following demo also uses this way);

Binary heap related operations

The basic structure of the heap

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity){ data = new Array<>(capacity); }
    public MaxHeap(a){ data = new Array<>(); }
    // Returns the number of elements in the heap
    public int size(a){ return data.getSize(); }
    // Returns a Boolean value indicating whether the heap is empty
    public boolean isEmpty(a){ return data.isEmpty(); }
    // Returns the index of the parent node of the element represented by an index in the array representation of a complete binary tree
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }
    // Returns the index of the left child node of the element represented by an index in the array representation of a complete binary tree
    private int leftChild(int index){ return index * 2 + 1; }
    // Returns the index of the right child node of the element represented by an index in the array representation of a complete binary tree
    private int rightChild(int index){ return index * 2 + 2; }}Copy the code

Add elements and Sift Up to the heap

When an element is inserted into the heap it may not satisfy the properties of the heap. In this case the position of the element in the heap needs to be adjusted so that it becomes a heap again. This process is called heapifying. If the basic properties of the heap are not satisfied, the position of the two elements is changed and the process is repeated until each node satisfies the properties of the heap. Let’s simulate the process below:

Let’s insert a new element 26 into the heap:

We can easily find the parent node of the newly inserted element using the index (above), compare their size, and swap the two elements if the new element is larger. This operation is equivalent to floating the element up:

Repeat this operation until 26 reaches a position where the heap condition is satisfied, at which point the insert is complete:

The corresponding code is as follows:

// Add elements to the heap
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k){

    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){ data.swap(k, parent(k)); k = parent(k); }}Copy the code

Extract the largest element in the heap and Sift Down

If understanding of the process, then take out the pile top (heap element) of the largest elements will become easy, applied to a tip here, though, is to use the last element to replace the element of the stack, and then put the last element removed, so the total number of elements also meet the conditions, then only need to elements in the stack, in turn, to adjust good, This operation is called Sift Down:

Replace the top element with the last element, then delete the last element:

Then compare the size of its child nodes:

If the heap condition is not met, then swap places with the larger child node:

Repeat this step until 16 reaches the appropriate position:

To complete the extraction of the largest element:

The corresponding code is as follows:

// Look at the largest element in the heap
public E findMax(a){
    if(data.getSize() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty.");
    return data.get(0);
}

// Fetch the largest element in the heap
public E extractMax(a){

    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

private void siftDown(int k){

    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); // In this loop,data[k] and data[j] switch places
        if( j + 1 < data.getSize() &&
                data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;
        // Data [j] is the maximum value of leftChild and rightChild

        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break; data.swap(k, j); k = j; }}Copy the code

The Replace and Heapify

Replace takes the largest element out of the heap and then inserts a new element into the heap. The conventional way is to Sift Up the heap using the same operation as before, but a trick is to simply Replace the top element with the new element. Sift Down is then applied to transform two O(logn) operations into one O(logn) :

// Take the largest element in the heap and replace it with element e
public E replace(E e){
    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}
Copy the code

Heapify heap is the translation of meaning, is sorting piles of arbitrary array shape, the usual approach is to iterate through group starting from 0 to add to create a new pile, but there’s a trick is the current array is seen as a complete binary tree, and then from the last leaf node began to Sift Down operation is ok, The last non-leaf node is also easy to find, which is the parent of the last node. You can verify this:

Sift Down operations start from node 22:

Repeat this process up to the top of the heap element:

Complete heap operation:

To insert n elements into an empty heap one by one, the algorithm complexity is O(nlogn), while heapify’s process, the algorithm complexity is O(n), which is a quantum leap, here is the code:

public MaxHeap(E[] arr){
    data = new Array<>(arr);
    for(int i = parent(arr.length - 1); i >=0 ; i --)
        siftDown(i);
}
Copy the code

Heap-based priority queues

Our Queue still needs to inherit the interface Queue we declared earlier, and then implement the methods in this interface.

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(a){ maxHeap = new MaxHeap<>(); }
    @Override
    public int getSize(a){ return maxHeap.size(); }
    @Override
    public boolean isEmpty(a){ return maxHeap.isEmpty(); }
    @Override
    public E getFront(a){ return maxHeap.findMax(); }
    @Override
    public void enqueue(E e){ maxHeap.add(e); }
    @Override
    public E dequeue(a){ returnmaxHeap.extractMax(); }}Copy the code

In Java PriorityQueue

Java.util.PriorityQueue: java.util.PriorityQueue: java.util.PriorityQueue: java.util.PriorityQueue: java.util.PriorityQueue In addition, if you want to change the smallest heap to the largest heap, you can pass your own comparator to PriorityQueue, for example:

// Default PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(5); pq.add(2); pq.add(1); pq.add(10); pq.add(3); while (! pq.isEmpty()) { System.out.println(pq.poll() + ", "); } System.out.println(); System. The out. Println (" -- -- -- -- -- -- -- -- -- -- -- -- "); Pq2 = new PriorityQueue<>((a, b) -> b - a); pq2.add(5); pq2.add(2); pq2.add(1); pq2.add(10); pq2.add(3); while (! pq2.isEmpty()) { System.out.println(pq2.poll() + ", "); }Copy the code