堆实现

Question

在ADT优先级队列的堆实现中，具有最高优先级值的项始终位于数组的前端或根部？

或者，具有最高优先级值的ADT优先级队列位于阵列的n-1个插槽中？

Answer 1

在实现优先级队列的方式中，最高优先级值始终位于数组的第一个(第零个)位置。它们通常以堆的形式实现：

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

这是因为父级很容易通过

(index - 1) / 2 

(使用整数除法时)

Answer 2

您可以取消优先级并获得您想要的东西。

但是说n-1插槽是不正确的，因为如果你指的是std::priority_queue类模板，它是一个实现细节(在本例中是C++)。这已经不是ADT的问题，而是实现细节的问题。

实际上，您可以将其用于您的目的:例如，int的通常优先级队列是std::priority_queue<int>，但优先级相反的是std::priority_queue<int, std::vector<int>, std::greater<int> >