algorithm - 尝试检查树是否是最大堆

Question

首先我将 Heap 插入到一个 Array 中(根据 Level order(又名 Breadth first)遍历)，现在我检查数组

 For i = 1 to Len(Array) do:
         IF 2 * i smaller than Len(Array):
            IF Array[i] smaller than Array[2i] OR Array[i] larger than  Array[2i+1]:
                 Return false
         Else if 2 * i larger than Len(Array):
            Return True

但我的问题是算法只有在树是完全二叉树时才有效，如果不热我可以改进我的代码吗？？

Answer 1

Array[i] larger than  Array[2i+1]

检查不应该是相反的吗:

Array[i] smaller than  Array[2i+1]

我认为你那里有一个错误。

此外，您还有其他问题。

例如循环完成后做“return true”。

试试这个伪代码:

For i = 1 to Len(Array) do:
BEGIN

IF 2 * i + 1 <= Len(Array)
         IF ( Array[i] smaller than Array[2i] ) OR ( Array[i] smaller than Array[2i+1]):
                 Return false
ELSE IF 2 * i <= Len(Array):
         IF Array[i] smaller than Array[2i]:
                 Return false
ELSE:
    break // break from the loop 

END

RETURN TRUE;