Heap Implementations

Question

In a heap implementation of the ADT priority queue, the item with the highest priority value is always in the front or root of the array?

Or is it, where the ADT priority queue that has the highest priority value is in the n-1 slot of the array?

Answer 1

The way Priority Queues are implemented, the highest priority value is always at the first (zeroth) position of the array. They are typically implemented as a heap:

index  0 1 2 3 4 5 6 7 8 9
parent / 0 0 1 1 2 2 3 3 4

This is because the parent is easily found by

(index - 1) / 2

(when using integer division)

Answer 2

You can negate priority and obtain what you want.

But it is not correctly to say about n-1 slot because it is an implementation details (in this case in C++) if you mean std::priority_queue class template. And this is already not about ADT but implementation details.

You actually can use it for your purpose: E.g. usual priority queue for int's is std::priority_queue<int>, but with opposite priorities is std::priority_queue<int, std::vector<int>, std::greater<int> >