以下堆假设都是最大堆。
维护堆的性质的函数：将当前点与左右孩子比较，若孩子更大，将较大的孩子与当前节点交换位置，当前节点被换到的子节点继续用此方法，直到叶节点或不需要交换。
若共有n个元素，则每次调用该方法的时间复杂度为O(lgn)。建堆过程需要自底向上将所有元素都调用一遍该方法，看起来时间复杂度应为O(nlgn),但这个上界虽然正确，却不是渐进紧确的，有很大一部分的节点高度并没有达到lgn。
设n个元素，高度为lgn，堆中高度为h的元素最多有n/2^(h+1)个（h从0开始计数），高度为h的节点调用上述方法的时间复杂度为O（h），则总时间代价为：
其中，Ai为所有j<i，i与j不同生日的事件。则：
则有递归式：
任意子数组必然是以下三种情况之一：
1.完全在a[low…mid]中。
2.完全在a[mid+1…high]中。
3.跨越了数组中点。
若结果为1或2，则可通过递归求解，若结果为3，则可通过一个线性时间复杂度的函数求解：