堆中的父级是否有子级

Question

我正在尝试检查Max-Heap，以查看父对象是否有子对象。我的堆被实现为一个向量。首先，我编写了一个bool (Int)函数，hasChildren是父对象在堆中的位置。我的主要条件是：

if(heap[2*loc + 1] == NULL && heap[2*loc + 2] == NULL)   //if there are children

问题是你不能检查出边界索引...我想过指针算法，但那也是无效的。有没有人有关于如何检查堆中的父级是否有子级的建议？

谢谢!

Answer 1

问题是您不能检查超出界限的索引

如果这是一个std::vector，您可以使用它的at成员函数并捕获std::out_of_range异常。

Answer 2

你知道malloc的heap有多大吗？如果是这样，只需确保2*loc+1和2*loc+2在该范围内。如果将heap的malloc设置为N个元素，请确保2*loc+1和2*loc+2小于N：

if(((2*loc+1 < N) && (heap[2*loc + 1] == NULL)) &&
   ((2*loc+2 < N) && (heap[2*loc + 2] == NULL)))