Mark and Compact a Heap-Indexed Subtree

Problem Statement

You are given an array heap of integers representing a binary tree stored as a heap. In this representation, the node at index i has its left child at 2*i + 1 and its right child at 2*i + 2.

Given an index target and the heap array, perform the following two operations without mutating the original input:

1. Marking: Identify the target node and all of its descendants in the tree. Create a new array where these nodes are replaced with the value -1.
2. Compacting: Create a second array containing only the elements that were not marked (i.e., those that were not the target or its descendants), maintaining their original relative order.

Function Signature

def process_heap(heap: List[int], target: int) -> Tuple[List[int], List[int]]:

Constraints

• 0 <= target < len(heap)
• heap length up to 10^5
• Elements in heap are non-negative integers.

Examples

Example 1: Input: heap = [10, 20, 30, 40, 50], target = 1

• Node 1 (value 20) has children at 2*1+1=3 (value 40) and 2*1+2=4 (value 50).
• Marked: Indices {1, 3, 4}.
• Marked Array: [10, -1, 30, -1, -1]
• Compacted Array: [10, 30]

Example 2: Input: heap = [5, 2, 8], target = 0

• Node 0 has children at 1 and 2. All nodes are marked.
• Marked Array: [-1, -1, -1]
• Compacted Array: []

Edge Cases

• target is a leaf node.
• target is the root node.
• heap is empty or contains a single element.