面试算法——

堆

堆（Heap） 是一种特殊的数据结构，它通常用于实现优先队列。堆分为大根堆和小根堆两种类型。大根堆要求每个节点的值都不大于其父节点的值，因此最大的元素总是位于根节点上。小根堆要求每个节点的值都不小于其父节点的值，因此最小的元素总是位于根节点上。

堆通常被实现为一维数组，节点之间的关系可以用数组下标来表示。假设某个节点的下标为$i$，则它的父节点下标为$(i-1)\mathrm{/}2$，左子节点下标为$2i+1$，右子节点下标为$2i+2$。这种数组实现方式比较紧凑，不需要额外的指针来表示节点之间的关系，因此空间复杂度比链表实现方式低。

堆的常用操作包括插入元素、删除堆顶元素、堆化等。插入元素通常是将元素添加到堆的末尾，然后通过上滤操作将其移动到正确的位置。删除堆顶元素通常是将堆顶元素和堆末尾的元素交换，然后删除堆末尾的元素，再通过下滤操作将新的堆顶元素移动到正确的位置。堆化是指将一个无序数组转换为一个堆的过程，通常使用下滤操作从最后一个非叶子节点开始，依次将子树调整为堆。

堆的时间复杂度取决于堆的高度，也就是树的深度。由于堆通常是一棵完全二叉树，因此堆的高度为logN，其中N为元素个数。因此，堆的插入、删除、查找最值等基本操作的时间复杂度均为$O(logN)$。堆排序也是一种基于堆的排序算法，其时间复杂度为$O(NlogN)$。

heapq

heapq 是 Python 内置的一个用于实现堆的模块，提供了一些对堆的基本操作，包括建堆、插入元素、弹出最小值等。以下是一些常用的 heapq 方法：

• heapq.heappush(heap, x)：将元素 x 压入堆中。

• heapq.heappop(heap)：从堆中弹出最小元素，并将其从堆中删除。

• heapq.heappushpop(heap, x)：先将元素 x 压入堆中，再弹出并返回堆中最小元素。

• heapq.heapreplace(heap, x)：弹出并返回堆中最小元素，并将元素 x 压入堆中。

• heapq.heapify(x)：将列表 x 原地转换为一个小根堆。

• heapq.nlargest(n, iterable[, key])：返回一个可迭代对象中第 n 大的元素。

• heapq.nsmallest(n, iterable[, key])：返回一个可迭代对象中第 n 小的元素。

其中，参数 heap 是堆，可以是列表，也可以是其他可迭代对象，但需要先通过 heapq.heapify() 方法将其转换为堆。key 参数是一个可调用对象，用于提取元素的键值。

用Python刷堆的题属实是没什么意思的，建议有条件的还是自己实现不要调用库函数了。

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        res = heapq.nlargest(k, nums)
        return res[-1]

如果你觉得上边这个代码太无耻了，你可以用下边这个：

class Solution:
    def findKthLargest(self, nums, k: int) -> int:
        # res = heapq.nlargest(k, nums)
        # return res[-1]
        heap = []
        for i in range(len(nums)):
            if len((heap)) < k:
                heapq.heappush(heap, nums[i])
            elif nums[i] > heap[0]:
                heapq.heapreplace(heap, nums[i])
        return heap[0]

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

不讲武德：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [item for item, _ in Counter(nums).most_common(k)]

讲武德，也没什么用：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        n = Counter(nums)
        res = heapq.nlargest(k, n, key=n.get)
        return res

首先，Counter(nums) 的时间复杂度为 $O(n)$，其中 $n$ 是数组 nums 的长度。

接下来，heapq.nlargest(k, n, key=n.get) 的时间复杂度为 $O(n\log k)$，其中 $k$ 是要求的前 k 个元素的个数，$n$ 是不同元素的个数。由于 Counter 对象 n 的元素个数不超过 nums 数组的长度，因此 $n\le m\le n^2$，其中 $m$ 是数组 nums 中的不同元素的个数。因此，heapq.nlargest(k, n, key=n.get) 的时间复杂度为 $O(\min (n\log k,nm\log k))$。

因此，总的时间复杂度为 $O(\min (n\log k,nm\log k))$，空间复杂度为 $O(n)$，即用于存储 Counter 对象 n 的空间。

373. 查找和最小的 K 对数字

给定两个以 升序排列 的整数数组 nums1 和 ****nums2 ****, 以及一个整数 k ****。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 ****。

请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3 
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

提示:

• 1 <= nums1.length, nums2.length <= 105
• -109 <= nums1[i], nums2[i] <= 109
• nums1 和 nums2 均为升序排列
• 1 <= k <= 1000

我们可以将所有的可能的数对进行遍历，并计算它们的和。然后，我们可以将数对按照它们的和从小到大排序，并返回前 k 个数对。

但是，这种方法的时间复杂度为 $O(n^2\log n)$，其中 $n$ 是数组的长度，因此当 $n$ 较大时，时间复杂度将非常高。所以我们需要使用一种更加高效的算法。

一种高效的算法是使用小根堆。我们将第一个数组 nums1 中的所有元素和第二个数组 nums2 中的第一个元素形成的数对 (nums1[i],nums2[0]) 放入小根堆中。然后，对于小根堆中的前 k 个数对中的某个数对 (nums1[i],nums2[j])，我们将下一个可能成为答案的数对 (nums1[i],nums2[j+1]) 放入堆中。这样，我们可以避免遍历所有的数对，并只保留可能成为答案的数对。

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = []
        # 将 nums1 中的前 min(k, len(nums1)) 个元素与 nums2 中的第一个元素组成数对，放入堆中
        for i in range(min(k, len(nums1))):
            heapq.heappush(heap, (nums1[i]+nums2[0], i, 0))
        
        res = []
        # 重复取出堆中最小的数对，将其加入答案列表中，直到答案列表中有 k 个数对
        while heap and k > 0:
            _, i, j = heapq.heappop(heap)
            res.append([nums1[i], nums2[j]])
            if j+1 < len(nums2):
                # 将 nums1[i] 与 nums2[j+1] 组成数对，放入堆中
                heapq.heappush(heap, (nums1[i]+nums2[j+1], i, j+1))
            k -= 1
        
        return res

时间复杂度：$O(k\ast log(min(k,len(nums1))))$，其中 k 是返回的数对数量，nums1 中有 $min(k,len(nums1))$ 个数需要组合。

空间复杂度：$O(min(k,len(nums1)))$，即堆的大小。