3

To build heap, we use PriorityQueue class in java. Is there a way using inbuilt library/class to build heap directly from an array in O(N) instead of pushing each element individually to build heap in O(NlogN)?

Zephyr
  • 1,521
  • 3
  • 22
  • 42
  • 3
    @Razib, No,it's not a duplicate. In java, we can't take entire array at a time and build heap in O(n) (as per my knowledge) . We have to insert each element of the array individually into the heap and that takes O(NlogN). So my question is, is there a way to take the entire array and build heap in O(N) ? I am well aware of the fact that time complexity required to build heap from an array is O(N). – Zephyr May 20 '19 at 20:01
  • I voted to reopen since the marked dupe explains why it's computationally possible, and not how to do it with Java's built-in PriorityQueue – that other guy May 20 '19 at 20:41

1 Answers1

14

Use the constructor that takes a collection:

new PriorityQueue<String>(Arrays.asList(yourArray));

True to form, the Java Docs don't mention anything about complexity, but reading the source code shows that the OpenJDK uses the typical O(n) heapify approach rather than inserting in a loop:

private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}
that other guy
  • 116,971
  • 11
  • 170
  • 194
  • Actually I want to build heap of objects. I don't find a constructor where we can pass both collection and comparator as parameters. Is there any workaround for that? – Zephyr May 20 '19 at 20:21
  • 1
    The only workaround I see is to wrap the objects in something that inherits Comparable and uses the comparator. At that point you might as well copy-paste a heapify algorithm instead of using PriorityQueue – that other guy May 20 '19 at 20:37