Explain Heap, Bottom-up Heap and Top-down heap with example.

3. Explain Heap, Bottom-up Heap and Top-down heap with example.

Answer:

A heap is a binary tree that satisfies two main conditions:

1. Shape Property: The tree is complete—all levels are full, except possibly the last, which is filled from left to right.
2. Heap Property (Parental Dominance): The key in each node is greater than or equal to its children.
   (Automatically true for leaves.)

Properties of Heaps

1. Exactly one complete binary tree exists for n nodes.
2. Root always contains the largest element.
3. Any subtree (node and its descendants) is also a heap.
4. A heap can be stored in an array H[1..n] with:
   • Parents in first n/2 positions.
   • Children of node at position i in 2i and 2i+1.
   • Parent of node at i is at position i/2.

Heap Property in Array Form:

H[i] ≥ max(H[2i], H[2i+1]) for all i = 1 to n/2

Bottom-Up Heap Construction

1. Place the list of n keys in level-order into a complete binary tree.
2. Start from the last parent node and “heapify”:
   • Compare parent with children.
   • Swap with larger child if needed.
   • Repeat until parental dominance is satisfied.

Bottom-up heap construction for input: 2, 9, 7, 6, 5, 8.

Worst-Case Efficiency:

• Total comparisons in worst case ≈ 2(n − log₂(n + 1))
• Hence, time complexity: O(n)

Top-Down Heap Construction (Insertion Method)

1. Insert key K as the last leaf.
2. “Sift up” by comparing with parent:
   • If parent ≥ K, stop.
   • Else, swap and continue up.

Inserting 10 into the heap—sift-up process.

Time Complexity: O(log n) (height of the heap)

Deleting the Maximum (Root) Key

1. Swap root with last key K.
2. Reduce heap size by 1.
3. “Sift down” K by swapping with the larger child until heap property is restored.

Deleting the root’s key and restoring heap structure.

Time Complexity: O(log n)