Heap Order Property

  • Describe the order property of a binary heap.

The ordering can be one of two types:

  • The min-heap property: the value of each node is less than or equal to the value of its children, with the minimum-value element at the root.
    (Here, "best" means "smallest.")

  • The max-heap property: the value of each node is greater than or equal to the value of its children, with the maximum-value element at the root.
    (Here, "best" means "largest.")

Exercise Which of the following is a valid binary max heap?

Solution

The two on the top are valid binary max heaps, but the bottom two are not. The bottom left is a min-heap. The bottom right violates the heap order property (200 should be at the root).