How to build max heap in O(n) time from a given array in java by using PriorityQueue collection?

Question

I am trying to find Kth largest element in a given array of size n. My idea: Build a maxheap from the given array (which takes O(n) time). And then remove (k-1) elements from the maxheap. finally return the topmost element in the heap.

I know I can build heap by taking elements from array one by one, but that will take O(nlogn) time to build heap.

 public int findKthLargest(int[] nums, int k) {
       
        //max heap
        PriorityQueue<Integer> pq;
       // pq = how to build pq from nums in O(n) time??
        
        while(k>1){
            pq.poll();
        }
        
        return pq.peek();
    }

How can I build maxheap in O(n) time?

Answer 1

1) How to Build MinHeap in O(n) Using PriorityQueue of Java?

You should construct the PriorityQueue with a Collection rather than using one-by-one approach. Use Arrays package to convert your array to List.

PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(nums));

It utilizes sink based approach to create a pq in O(n) time complexity. Although not the same, creating a pq with an array can be implemented like this:

 public MinPQ(int[] keys) {
   n = keys.length;
   pq = new int[keys.length + 1];
   for (int i = 0; i < n; i++)
        pq[i+1] = keys[i];
   for (int k = n/2; k >= 1; k--)
        sink(k);
    }

private void sink(int k) {
   while (2*k <= n) {
      int j = 2*k;
      if (j < n && pq[j] > pq[j + 1]) j++;
      if (pq[k] <= pq[j]) break;
      exch(k, j);
      k = j;
    }
  }
private void exch(int i, int j) {
    int swap = pq[i];
    pq[i] = pq[j];
    pq[j] = swap;
}

It's just an example to show how constructor should be implemented for O(n) time complexity. You do not need to implement them, they are already implemented in PQ.

2) How to Build MaxHeap in O(n) Using PriorityQueue of Java?

Well, unfortunately you cannot pass a Comparator and a Collection to the Java's PQ at the same time. What you can do is to write your own PQ which extends the Java's PQ (a majority of the methods will stay the same). One beautiful implementation can be found here.
Implementation below uses the fact that:

public PriorityQueue(PriorityQueue<? extends E> c)
Creates a PriorityQueue containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue.

Thanks to @samabcde:

import java.util.*;

public class CustomComparatorPriorityQueue<T> extends PriorityQueue<T> {
    private Collection<T> wrapped;

    public static <U> PriorityQueue<U> create(Collection<U> wrapped, Comparator<U> custom) {
        return new PriorityQueue<U>(new CustomComparatorPriorityQueue<>(wrapped, custom));
    }

    private CustomComparatorPriorityQueue(Collection<T> wrapped, Comparator<T> custom) {
        super(custom);
        this.wrapped = wrapped;
    }

    @Override
    public Object[] toArray() {
        return wrapped.toArray();
    }

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(3, 6, 4, 8, 1, 9);
        PriorityQueue<Integer> pq = CustomComparatorPriorityQueue.create(a, Comparator.<Integer>naturalOrder().reversed());
        Integer b;
        while ((b = pq.poll()) != null) {
            System.out.println(b);
        }
    }

}

Java's PQ related constructor:

public PriorityQueue(PriorityQueue<? extends E> c) {
    this.comparator = (Comparator<? super E>) c.comparator();
    initFromPriorityQueue(c);
}

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
    if (c.getClass() == PriorityQueue.class) {
        this.queue = ensureNonEmpty(c.toArray());
        this.size = c.size();
    } else {
        initFromCollection(c);
    }
}

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
 }

/**
 * Establishes the heap invariant (described above) in the entire tree,
 * assuming nothing about the order of the elements prior to the call.
 * This classic algorithm due to Floyd (1964) is known to be O(size).
 */
private void heapify() {
    final Object[] es = queue;
    int n = size, i = (n >>> 1) - 1;
    final Comparator<? super E> cmp;
    if ((cmp = comparator) == null)
        for (; i >= 0; i--)
            siftDownComparable(i, (E) es[i], es, n);
    else
        for (; i >= 0; i--)
            siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}

Conclusion

In short, you can create MinHeap in O(n) with one line of code, to create MaxHeap in O(n) you should rather implement your own MaxHeap from scratch or implement a subclass that exploits the property of PriorityQueue(PriorityQueue<? extends E> c), that mentioned above.