Implementation of Priority Queue

A priority queue is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.

A common misconception is that a Heap is the same as a Priority Queue, which is not true. A priority queue is an abstract data type, while a Heap is a data structure. Therefore, a Heap is not a Priority Queue, but a way to implement a Priority Queue.

There are multiple ways to implement a Priority Queue, such as array and linked list. However, these implementations only guarantee O(1) time complexity for either insertion or deletion, while the other operation will have a time complexity of O(N)O(N). On the other hand, implementing the priority queue with Heap will allow both insertion and deletion to have a time complexity of O(logN).

Priority Queue/Heap 维护了一个每次poll都是最小元素。是用complete binary tree实现。

所谓的"完全二叉树", 要满足:

• 除了最后一层, 所有层都排满(没有非空节点)

• 最后一层的所有非空节点都排在左边

一张图可以直观说明, 完全二叉树其实就是长得像这样:

A heap is a binary tree that meets the following criteria:

• Is a complete binary tree;

• The value of each node must be no greater than (or no less than) the value of its child nodes.

There are two kinds of heaps: Max Heap and Min Heap.

• Max Heap: Each node in the Heap has a value no less than its child nodes. Therefore, the top element (root node) has the largest value in the Heap. (value of node >= values of children)

• Min Heap: Each node in the Heap has a value no larger than its child nodes. Therefore, the top element (root node) has the smallest value in the Heap. (value of node <= values of children)

min heap 操作：

• peek(): 返回数组的第一个元素的值，root节点总是最大/小值。time complexity: O(1)

• insert(): 插入一个新的元素，总是放在数组元素的最后一个位置，然后heapifyUp，调整heap满足min heap。time complexity: O(logN)

• poll(): 拿出数组的第一个元素，heap中剩下的元素要进行调整，保证heap是min heap的结构，这个过程是heapifyDown。time complexity: O(logN)

• heapifyUp: 数组新增的最后一个元素与其parent进行比较， 如果新增元素的值小于其parent的值，则进行交换，递归此过程。时间复杂度是O(lgn)。

• heapifyDown: 把最后一个元素放到root的位置，从root位置开始，比较root位置代表的parent与其左右children的大小，parent总是与children中元素较小的进行交换。 重复这个过程，直到大的元素不再有children。时间复杂度是O(lgn)。

• build树的时候，因为有n个node，每加入一个都要heapify，所以时间复杂度是O(nlgn)

public class MinHeap {
    // Create a complete binary tree using an array
    // Then use the binary tree to construct a Heap
    int[] minHeap;
    
    // the number of elements is needed when instantiating an array
    // heapSize records the size of the array
    int heapSize;
    
    // realSize records the number of elements in the Heap
    int realSize = 0;

    public MinHeap(int heapSize) {
        this.heapSize = heapSize;
        minHeap = new int[heapSize + 1];
        // To better track the indices of the binary tree, we will not use the 0-th element in the array
        // You can fill it with any value
        minHeap[0] = 0;
    }

    // Function to add an element
    public void add(int element) {
        realSize++;
        
        // If the number of elements in the Heap exceeds the preset heapSize
        // print "Added too many elements" and return
        if (realSize > heapSize) {
            System.out.println("Added too many elements!");
            realSize--;
            return;
        }
        
        // Add the element into the array
        minHeap[realSize] = element;
        
        // Index of the newly added element
        int index = realSize;
        
        // Parent node of the newly added element
        // Note if we use an array to represent the complete binary tree and store the root node at index 1
        // - index of the parent node of any node is [index of the node / 2]
        // - index of the left child node is [index of the node * 2]
        // - index of the right child node is [index of the node * 2 + 1]
        int parent = index / 2;
        // If the newly added element is smaller than its parent node,
        // its value will be exchanged with that of the parent node 
        while ( minHeap[index] < minHeap[parent] && index > 1 ) {
            int temp = minHeap[index];
            minHeap[index] = minHeap[parent];
            minHeap[parent] = temp;
            index = parent;
            parent = index / 2;
        }
    }

    // Get the top element of the Heap
    public int peek() {
        return minHeap[1];
    }

    // Delete the top element of the Heap
    public int pop() {
    
        // If the number of elements in the current Heap is 0,
        // print "Don't have any elements" and return a default value
        if (realSize < 1) {
            System.out.println("Don't have any element!");
            return Integer.MAX_VALUE;
        } else {
            // When there are still elements in the Heap
            // realSize >= 1
            int removeElement = minHeap[1];
            
            // Put the last element in the Heap to the top of Heap
            minHeap[1] = minHeap[realSize];
            realSize--;
            int index = 1;
            
            // When the deleted element is not a leaf node
            while (index <= realSize / 2) {
            
                // the left child of the deleted element
                int left = index * 2;
                
                // the right child of the deleted element
                int right = (index * 2) + 1;
                
                // If the deleted element is larger than the left or right child,
                // its value needs to be exchanged with the smaller value of the left and right child
                if (minHeap[index] > minHeap[left] || minHeap[index] > minHeap[right]) {
                    if (minHeap[left] < minHeap[right]) {
                        int temp = minHeap[left];
                        minHeap[left] = minHeap[index];
                        minHeap[index] = temp;
                        index = left;
                    } else {
                        // maxHeap[left] >= maxHeap[right]
                        int temp = minHeap[right];
                        minHeap[right] = minHeap[index];
                        minHeap[index] = temp;
                        index = right;
                    }
                } else {
                    break;
                }
            }
            return removeElement;
        } 
    }

    // return the number of elements in the Heap
    public int size() {
        return realSize;
    }

    public String toString() {
        if (realSize == 0) {
            return "No element!";
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = 1; i <= realSize; i++) {
                sb.append(minHeap[i]);
                sb.append(',');
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append(']');
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        // Test case
        MinHeap minHeap = new MinHeap(3);
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(2);
        // [1,3,2]
        System.out.println(minHeap.toString());
        // 1
        System.out.println(minHeap.peek());
        // 1
        System.out.println(minHeap.pop());
        // [2, 3]
        System.out.println(minHeap.toString());
        minHeap.add(4);
        // Add too many elements
        minHeap.add(5);
        // [2,3,4]
        System.out.println(minHeap.toString());
    }
}