堆
堆是一棵树：其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值，分别叫做最小堆/最大堆。
一般来说，我们在说到堆的时候往往指的是二叉堆：它是一颗完全二叉树形成的堆。下面是一个简易的实现：
// 这个过程也叫 heapify
void sink(vector<int> &nums, int i) {
int size = nums.size();
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && nums[left] > nums[largest]) {
largest = left;
}
if (right < size && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
std::swap(nums[i], nums[largest]);
sink(nums, largest);
}
}
void make_heap(vector<int> &nums) {
for (int i = nums.size() / 2 - 1; i >= 0; i--)
sink(nums, i);
}
int pop_heap(vector<int> &nums) {
int result = nums[0];
nums[0] = nums.back();
nums.pop_back();
sink(nums, 0);
return result;
}
void push_heap(vector<int> &nums, int num) {
nums.push_back(num);
int index = nums.size() - 1;
while (index > 0) {
int parent = (index - 1) / 2;
if (nums[index] > nums[parent]) {
std::swap(nums[index], nums[parent]);
index = parent;
} else {
break;
}
}
}
- 由于堆是完全二叉树，所以用数组来实现他是很合适的，不会浪费空间。
- 下沉操作（
sink）：如果当前节点的值小于其子节点的值，则将其与最大的子节点交换，并递归地继续下沉操作。时间复杂度为\(O(log (n))\)。 - 将一个无序数组创建成堆：从最后一个非叶子节点开始，对每个节点应用下沉操作（Sink），以确保子树满足最大堆的属性。时间复杂度为\(O(n)\)，后面解释。
- 向堆中插入元素：将元素放在最后一个节点，进行“提升操作”，如果当前节点的值大于其父节点的值，则将其与父节点进行交换，并递归的继续提升操作。时间复杂度同下沉操作，\(O(log (n))\)。
- 弹出堆的最大值：最大值就是堆顶/树根。将它与最后一个节点交换，然后对树根进行下沉操作。时间复杂度为\(O(log (n))\)。
尽管sink操作的时间复杂度是\(O(log(n))\)，而建堆要进行\(n/2\)次操作，但是将所有操作放在一起综合考虑，按照层进行考虑。第k层有\(2^k\)个元素，sink操作的时间复杂度是\(O(k)\)
\(\(T = \sum_{k=1}^{log (n)} 2^kk\)\) 可以使用错位相减法（等差乘等比，死去的高中记忆开始攻击我）求得\(O(T) = O(n)\)。
还看到了另一个巧妙的证明堆排序中建堆过程时间复杂度O(n)怎么来的？ - 工厂方法的回答 - 知乎。
元素动态改变的堆
利用堆，我们可以很快（\(O(log n)\)）找到数组中元素的最大值，或者第k大的值（执行k次pop操作）。
如果这个数组是不断变化的（数据流），我们依然可以很快的找到数组中元素的最大值。但是找第k大的值似乎不那么直观了。
先看一个简单的例子，数据流虽然不断变化，但是数据只增不删：703. 数据流中的第 K 大元素 - 力扣（LeetCode）。
这时我们只需要维护前k个最大元素的最小堆，堆顶就是第k大元素。
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.min_heap = []
self.k = k
for i in range(0, len(nums)):
self.add(nums[i])
def add(self, val: int) -> int:
if len(self.min_heap) < self.k:
heapq.heappush(self.min_heap, val)
return self.min_heap[0]
if self.min_heap[0] > val:
return self.min_heap[0]
else:
heapq.heappop(self.min_heap)
heapq.heappush(self.min_heap, val)
return self.min_heap[0]
这种方法不止适用于不断变化的数组，对于固定的数组求第K大元素，除了上面说的pop k次，也可以采用相同的方法。