Insert Element in a Heap

Blue Yonder fulfillment workloads prioritize jobs by the smallest priority value. Implement insertion into an indexed binary min-heap that stores jobs as [priority, sequence, job_id]. The heap must preserve lexicographic ordering by priority, then sequence, then job ID.

In addition to the heap array, maintain a position map so positions[job_id] always equals the job's current heap index. The input heap is valid, job_id is not already present, and both the heap and position map must be updated in place. Return [heap, positions] after insertion.

Formal Specification

Implement insert_job(heap, positions, job_id, priority, sequence).

• heap: a list of three-element lists, where each entry is [priority, sequence, job_id].
• positions: a dictionary mapping each existing job ID to its index in heap.
• job_id: the unique string identifier for the new job.
• priority: an integer priority, with smaller values processed first.
• sequence: a unique integer used to preserve arrival order when priorities match.
• Return the updated heap and position map as [heap, positions].

After insertion, every parent must be less than or equal to its children under the specified lexicographic ordering, and every job must map to its correct index.