2
$\begingroup$

Is it correct to call something with no elements a binary heap? I think it is correct, for one element too, but I'm not sure. It seems to satisfy the definition (from Wikipedia):

Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

Heap property: the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children, according to some total order.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You certainly need a smallest heap. Is it really important whether it's empty or a singleton? $\endgroup$
    – Raphael
    Commented Aug 8, 2016 at 8:52
  • $\begingroup$ @Raphael what do you mean? $\endgroup$
    – Celeritas
    Commented Aug 8, 2016 at 8:55

1 Answer 1

Reset to default
3
$\begingroup$

It's up to you to decide. It's a pathological case which is quite similar to the empty graph (on zero vertices) — sometimes it makes sense to admit it, and sometimes not. It depends on the circumstances. The definition in Wikipedia is irrelevant here — there are many other similar definitions in the literature, that might disagree on this point.

I recommend the classic article Is the null-graph a pointless concept by Harary and Read.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "No conclusion is reached." - heh... $\endgroup$
    – user11153
    Commented Aug 8, 2016 at 11:33
  • 2
    $\begingroup$ If I was making a library that included a heap implementation, I would certainly allow the empty case. Without thinking. $\endgroup$
    – John Dvorak
    Commented Aug 8, 2016 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.