Replay an Operation Log on a Max-Heap With a Replace-Top Command
Implement replayMaxHeap
Run a log of operations against an initially empty max-heap: insert a value, extractMax (remove and report the largest value), peekMax (report it without removing) and replaceMax — which removes the current largest value, adds a new value in its place, and reports the value it removed. Return the answer reported by every extractMax, peekMax and replaceMax, in order; any of them on an empty heap reports -1 (and replaceMax still adds its value).
Re-sorting the whole list before every query gives the right answers, but does far more work than the question needs. A binary max-heap keeps only the maximum in a known place and repairs itself along one path after each change — and replaceMax shows a neat shortcut: overwrite the root and sift down once, instead of extracting and inserting.
Example 1:
Input: ops = ["insert","insert","insert","replaceMax","extractMax","peekMax"], values = [4,9,6,5,0,0]
Output: [9,6,5]
Example 2:
Input: ops = ["insert","replaceMax","peekMax"], values = [3,20,0]
Output: [3,20]
Example 3:
Input: ops = ["replaceMax","peekMax","extractMax","extractMax"], values = [7,0,0,0]
Output: [-1,7,7,-1]
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ ops.length ≤ 100, and values.length equals ops.length - ●
Each op is "insert", "extractMax", "peekMax" or "replaceMax"; the matching values entry is only read for "insert" and "replaceMax" - ●
0 ≤ values[i] ≤ 1000 - ●
"replaceMax v" removes the current maximum, adds v, and reports the removed maximum; on an empty heap it just adds v and reports -1 - ●
"extractMax" and "peekMax" on an empty heap report -1
ops =
values =