Max Heap

A Max-Heap is a type of binary tree where the largest value is always at the top (the root), and each parent node is always greater than or equal to its child nodes.

There are some important rules that define a Max-Heap:

• The tree must be a complete binary tree. This means all levels of the tree are filled except maybe the last, and nodes are filled from left to right.

• Every parent node must be greater than or equal to its children.

• The largest value is always at the root.

Here’s a quick example:

        10
       /  \
      7    5
     / \   \
    1   3   4

How is a Max-Heap Different from a Binary Search Tree?

A Max-Heap is not the same as a BST. Here are the key differences:

1. Ordering:

• In a BST, the left child must be less than the parent, and the right child must be greater than the parent.

• In a Max-Heap, the only rule is that the parent is greater than the children — it doesn’t matter whether the child is on the left or right.