Welcome! This note is about a wonderful data structure - PriorityQueue (Heap).
I think I need to write by myself since I have been asked about heap sort in the real interview of Byte Dance. During that interview, I have some ideas, but not very clear. Therefore, I found that people cannot make impressive performance during an interview unless you can totally understand the whole information about one particular technical point.

I About Heap sort

Heap Sort Algorithm for sorting in increasing order:

  1. Build a max heap from the input data.
  2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.
  3. Repeat step 2 while size of heap is greater than 1.

How to build the heap?
Heapify procedure can be applied to a node only if its children nodes are heapified. So the heapification must be performed in the bottom-up order.

Examples:
Input data: 4, 10, 3, 5, 1

yVfnYj.png

The numbers in bracket represent the indices in the array representation of data.

Applying heapify procedure to index 1:

yVfnYj.png

Applying heapify procedure to index 0:

yVfufs.png
The heapify procedure calls itself recursively to build heap in top down manner.

Implement a PriorityQueue

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
public class PriorityQueue {

    public static class MaxPriorityQueue<Type extends Comparable<Type>> {       
        private Type[] items; //store the elem in the heap
        private int N;        //record the number of the heap
        public MaxPriorityQueue(int capacity) {
            this.items = (Type[]) new Comparable[capacity+1];
            N = 0;
        }

        //return the size of the heap
        public int size() {
            return N;
        }

        //check if the heap is empty
        public boolean isEmpty() {
            return N == 0;
        }

        //determine whether the current element of index i is less than index j. 
        private boolean isLess(int i, int j) {
            return items[i].compareTo(items[j]) < 0;
        }

        //swap the element of index i and index j
        private void swap(int i, int j) {
            Type tmp = items[i];
            items[i] = items[j];
            items[j] = tmp;
        }
        public void add(Type t) {
            items[++N] = t;
            swim(N);
        }

        //delete the max element of the heap, return the max
        public Type popMax() {
            Type max = items[1];
            swap(1, N); //swap the index 1 and index N;
            items[N] = null; //delete the last index element
            N--;//size -1
            sink(1);
            return max;
        }

        //Implement swim algo, let element of index k to find correct position
        private void swim(int k) {
            //if we reach the root of heap
            while (k > 1) {
                //compare the current element of index k and it's parent
                if (isLess(k / 2, k)) {
                    //if parent element is less than current, then swap
                    swap(k / 2, k);
                }
                k = k / 2;
            }
        }

        //Implement sink algo, let element of index k to find correct position
        private void sink(int k) {
            while (2 * k <= N) { //if reach the leaf element, then stop while loop
                int max = 2 * k;//find the max of child node
                if (2 * k + 1 <= N) {//if we can find left and right child
                    if (isLess(2 * k, 2 * k + 1)) {
                        max = 2 * k + 1; //find the max index of left and right child
                    }
                }
                //if the current element is bigger than max, break the loop
                if (!isLess(k, max)) {
                    break;
                }
                //if the current element is smaller than max, then swap
                swap(k, max);
                k = max;
            }
        }
    }
    public static void main(String[] args) {
        MaxPriorityQueue<Integer> pq = new MaxPriorityQueue<Integer>(4);
        pq.add(1);
        pq.add(2);
        System.out.println(pq.popMax());
    }
}