In Java PriorityQueue, why does children of queue[n] are queue[2*n+1] and queue[2*(n+1)]?

0
votes

Min-Heap implementation in Java is represented by PriorityQueue which, in turn, is backed by transient Object[] queue;

The quote from its javadoc is

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)].

Why not queue[2n] and queue[2n+1] as Tim Roughgarden states here https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/KKqlm/heaps-implementation-details-advanced-optional 08:00?

1
javapriority-queue
What will happen if we ask a child of the 0'th element? - Denis Zavedeev
@caco3 I'll answer 1 and 2. coursera.org/learn/algorithms-graphs-data-structures/lecture/… 08:00 - Pasha
It is for the PriorityQueue in java :) but if we would use 2n and 2n+1 we would get 0 and 1 which is not correct. Using 2n and 2n + 1 works for languages where indexes start at 1, but in Java they start at 0, that's the reason - Denis Zavedeev
@Pasha indexing in the video starts at 1, that's why the formulas are valid there but in java must be adjusted - Denis Zavedeev
Thank you @caco3, you can issue your comment as a standalone response - Pasha

1 Answers

1
votes

As caco3 mentions in the commments, if the elements in a priority queue are stored in an array, the designers of that priority queue data structure can decide to store the first item in the array at position 0 or position 1.

Putting the first item in position 0 means that children are in positions 2N + 1 and 2N + 2. When the first item is stored in position 1 the children are in positions 2N and 2N + 1.

Either choice can lead to a correct implementation. Starting at 0 saves a little space. But some people feel that the math and code is more elegant when starting at 1.