c++ - 堆二叉树是否必须完成才能成为堆？

Question

我对 C++ 中的堆有一点困惑，我想更好地理解它。

二叉树必须是完整的(满二叉树)才能被归类为堆吗？

堆一定是完全二叉树吗？教授的回答是否定的，但我没有和教授核实过。

网上资源state heaps的定义是必须是完全二叉树。我的教授说堆是具有两个特殊属性的二叉树。

Answer 1

我假设您特别关心二进制堆。

在键排序属性之上，二叉树的最低层必须是左对齐的，而上面的所有层都必须是满的才能被归类为二叉堆。最低级别不必是满的。这种二叉树通常表示为完整，如果最低层已满，则表示为完美。

但是，如果您担心 C++ 实现，我想确切的术语并不是您所追求的——二叉堆很适合使用数组轻松实现，而且它适用于完整的二叉树，而不仅仅是完美的二叉树。