Comments on: Java PriorityQueue (+ Code Examples)

By: Steffen

Steffen — Thu, 16 Jan 2025 15:18:11 +0000

"the time required to insert and extract from a heap.

Thus, the time complexity for both operations is: O(n log n)"

It should be O(log(n)),
according to my text books and
https://stackoverflow.com/questions/28819327/time-complexity-of-inserting-in-to-a-heap

By: Sven Woltmann

Sven Woltmann — Mon, 04 Sep 2023 08:05:25 +0000

In reply to Peter Hintenaus. Hi Peter, That's exactly what the article is saying: "The time required for enqueue and dequeue operations in the Java PriorityQueue is equal to the time required to insert and extract from a heap. Thus, the time complexity for both operations is: O(n log n)" Perhaps you are referring to this sentence? "Thus, the time complexity for the peek operation is: O(1)" This is about the *peek* operation - looking at the first element without removing it. Best wishes Sven

By: Peter Hintenaus

Peter Hintenaus — Tue, 29 Aug 2023 09:05:40 +0000

The complexity for removal is wrong. Besides taking the root, on has to reestablish the heap: one takes the last element puts it in the root and reheaps down until one reaches the base of the balanced binary tree which a heap really is. This takes also O(log n) steps. See for example Cormen, Leiserson Rivest Stein: Introduction to Algorithms