浅谈对顶堆
我们知道，堆是一种极有用的数据结构。它能在短时间内将数据维护成单调递增/递减的序列。但是这种“朴素堆”对于问题求解起到的效果毕竟是有限的。所以我们在朴素堆的基础上，进行深入思考和适当变形，使之能解决一些其他的用朴素堆解决不了的问题，并使思路变得简洁有效。
这篇随笔就堆中的一个分支——对顶堆进行讲解，读者在阅读前应该掌握堆的基本概念，以便于更好地理解对顶堆。
如果把堆中的大根堆想成一个上宽下窄的三角形，把小根堆想成一个上窄下宽的三角形，那么对顶堆就可以具体地被想象成一个“陀螺”或者一个“沙漏”，通过这两个堆的上下组合，我们可以把一组数据分别加入到对顶堆中的大根堆和小根堆，以维护我们不同的需要。
那么对顶堆是干嘛用的呢？
举一个例题：
给定N个数字，求其前i个元素中第K小的那个元素。
我们很容易想到用堆来维护这个单调递增的序列，如果使用数组实现的话，我们直接输入数组下标为K的元素即可。但我们使用的是堆，它的实现方式——优先队列是不支持任意点访问的，那么我们就无法进行单点查询。引申对顶堆的概念，我们可以这样解决问题：
优先队列虽然不支持任意点访问，但可以用O(1)的时间查询出堆顶元素，也就是说，我们只能通过维护对顶堆中两个堆的堆顶元素来进行单调性的维护。怎么办呢？
原理很简单：根据数学中不等式的传递原理，假如一个集合A中的最小元素比另一个集合B中的最大元素还要大，那么就可以断定：A中的所有元素都比B中元素大。所以，我们把小根堆“放在”大根堆“上面”，如果小根堆的堆顶元素比大根堆的堆顶元素大，那么小根堆的所有元素要比大根堆的所有元素大。
回到这个问题：我们要求第K小的元素，那么我们把大根堆的元素个数限制成K个，前K个元素入队之后，每个元素在入队之前先与堆顶元素比较，如果比堆顶元素大，就加入小根堆，如果没有的话，把大根堆的堆顶弹出，将新元素加入大根堆。这样就维护出一个对顶堆。它的作用在于找出第K小的元素。
同理，对顶堆还可以用于解决其他“第K小”的变形问题：比如求前i个元素的中位数等。
