[!info] related notes 算法面试题型 MOC

Heap Interview Problems

Merge k Sorted Lists

• Use a min-heap keyed by node value.
• Initialize heap with each list head.
• Pop smallest, append to result, then push its next.
• Reference: 合并K个有序链表

Maximum Overlapping Segments

• Sort segments by start.
• Use a min-heap of end points.
• For each segment:
  • For non-empty half-open intervals [start, end), pop ends <= start; touching endpoints do not overlap.
  • Push current end.
  • Heap size is overlap count at this point; track max.
• Reference: 线段最多重合问题

Min Operations to Halve Array Sum

• Use a max-heap.
• Repeatedly take current max, halve it, put back, accumulate reduction until reached half of total sum.
• Reference: 数组和减半最少操作

各题的堆不变量

题型	堆中保存什么	为什么可以取堆顶
合并有序链表	每条未耗尽链表的当前头节点	每条链表内部已非递减，全局最小必在这些头中
半开区间重叠	已开始且未结束的区间终点	最早结束的区间最先失活，堆大小表示当前数量
数组减半	每个数当前的值	当前值最大者本次减少量也最大，修改后需重新入堆

堆只负责取极值，排序前提、端点约定和贪心正确性仍由具体问题决定。

Related

• 堆与堆排序