关于最小绝对差堆解法的疑问：为何下一个最小值必在堆中？

首先明确前提：这个解法的第一步必然是将数组排序，所有推导都基于升序数组展开。

为什么下一个最小绝对差一定在堆中？核心逻辑如下：

• 对于升序数组，任意两个元素的差值 a[j] - a[i]（j > i），满足：固定i时，j越大差值越大；固定j时，i越小差值越大。所以每个i对应的最小差值必然是相邻的a[i+1]-a[i]，这也是全局最小差值的候选，因此初始堆中会放入所有相邻元素对的差值。
• 当弹出堆顶的最小差值对(i,j)（此时j = i+1），对于i来说，下一个可能的更小差值候选只能是(i,j+1)——因为j再增大的话，差值只会更大，而j减小就回到了同一元素（无意义）。
• 假设有一个不在堆中的元素对(m,n)（n > m+1），它的差值比堆中所有元素都小：

  因为数组升序，a[n]-a[m] > a[n-1]-a[m]，而(m,n-1)这个对要么已经被弹出过（弹出时会把(m,n)推入堆，矛盾），要么还在堆里（此时a[n-1]-a[m]更小，说明堆里有比假设更小的差值，矛盾）。

也就是说，所有可能的候选最小差值对，要么是初始的相邻对，要么是由已弹出的对衍生出的新对，这些都被加入了堆中，因此下一个最小差值必然存在于堆内。

内容的提问来源于stack exchange，提问作者nicku