CODEWITHSUNDEEP
javaheappriority-queue
SeleniteXin
SeleniteXin

Reputation: 23

Java: is there a way to construct a max-heap from an array in O(n) using PriorityQueue?

Correct me if I'm wrong, but I think the PriorityQueue(Collection c) constructor will create a min-heap from a collection in time O(n). However, I couldn't find a constructor where I can pass both a collection and a comparator (in order to convert the min-heap to a max-heap). So I was wondering if there is a way to construct a max-heap from an array (say, int array) in O(n) using PriorityQueue?

Upvotes: 2

Views: 182

Answers (1)

John Bollinger
John Bollinger

Reputation: 180181

No, having a set of elements arranged in a min-heap does not provide any advantage for rearranging them into a max-heap. Also, you seem to be assuming that the PriorityQueue constructors that accept a collection have O(n) asymptotic complexity. That's plausible -- even likely -- but it is not documented, so it is not safe to rely on it.

Upvotes: 1

Related Questions