Why is this binary tree not a heap?

Question

I have been teaching myself heaps for an exam and came across the following question:

"Give 2 different reasons why the following binary tree is not a heap"

    91
   /  \
  77  46
 /  \   \
68  81   11

I know one of the reasons this is because a heap's children must less than or equal to the value of its parent so 81 violates this rule as 81 > 77, but I am not sure on the other answer.

Could somebody please clarify?

Answer 1

11 should be the left-child of 46, not the right-child.

Wikipedia mentions that a binary heap should be a complete binary tree, which means "every level, except possibly the last, is completely filled, and all nodes are as far left as possible", which is clearly not the case if 11 is where it is now.

The reason why this is advantageous is fairly easy to understand - given the size of the heap, you can quickly determine where the last node on the bottom level is, which is necessary to know for insertion and deletion. If we're using an array representation, it's as simple as the element at heap size - 1 being the last element. For a pointer-based representation, we could easily determine whether we should go left or right to get to the last element.

There may be other ways to get the same performance without the heap being a complete binary tree, but they'd likely add complexity.

Answer 2

That is not a heap because it doesn't conform to the heap property.

• In a min-heap, every node's value is less than or equal to its child nodes' values.
• In a max-heap, every node's value is greater than or equal to its child nodes' values.

It's clearly not a min-heap because the root node, 91, is larger than either of its children. And it's clearly not a max-heap because the node 77 is smaller than its right child, 81.

And, as @Dukeling pointed out in his answer, it doesn't conform to the shape property.