Heap

Comparator Syntax:

PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(10, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b)
            {
                return a.compareTo(b);
            }
        });

        @Override
    public int compare(Cell a, Cell b)
    {
        if(a.value == b.value){
            return 0;
        }
        return a.value < b.value ? -1 : 1;
    }
});

10 - is capacity

Comparator here is Anonymous Inner Class. It can access instance variables and methods.

Heap related complexity

push/offer: O(logn) : put at last leaf, then siftUp

poll(): O(logn): poll from root of the tree, then take last leaf put at root position then do siftDown

how offer/poll work

heapify() an array represented binary tree: O(n) (explanation)

Heap array representation

For array index start from 0:(index as k)

• left child: 2k+1
• right child 2k+2
• parent (k-1)/2

For array index start from 1: (index as k)

• left child: 2k

• right child 2k+1

• parent k/2

Sift down/up implementation (over array representation)