堆

需求分析：

只要求数据集中的最大或最小值的元素，对于数据集中的其他元素，并不需要他们是有序的，这里就会使用堆

要点：

堆的数据结构和实现
最大堆，最小堆的基础概念和核心操作
堆排序
应用场景
解决实际问题

定义和分类

二叉树，并满足

完全二叉树
每一个节点的值都必须大于等于或小于等于其子节点的值

特点：

可以在 O(logN) 的时间复杂度内向堆中插入元素
可以在 O(logN) 的时间复杂度内向堆中删除元素
可以在 O(1) 的时间复杂度内获取堆的最大值或者最小值

堆的两种类型

最大堆：堆中每一个节点的值 都大于等于 其孩子节点的值。顶点最大。
最小堆：堆中每一个节点的值 都小于等于 其孩子节点的值。顶点最小。

插入操作：

最小堆的插入：
- 首先判断二叉树是不是最小堆
- 插入时要满足完全二叉树（从左往右插入）和节点值小于等于子节点值的特性（如果不满足则与父节点进行交换）
最大堆的插入类似

删除操作：

最大堆的删除：删除堆顶元素，即堆的最大值；然后将堆的最后一个元素放入堆顶，删除原最后一个元素；然后根据父节点和子节点的大小关系进行互换
最小堆的删除类似：

完全二叉树和数据转化

如何找到父节点：当前节点序号i，则父节点为i//2
如何找到右子节点和左子节点：当前节点序号i，右子节点为i*2，左子节点为i*2+1
如何确定一个叶子结点：当前节点序号i，大于n/2，n为所有节点个数

堆的常用方法：

创建最大堆，最小堆

创建一个堆实例，然后才能操作堆
或者同时进行堆化操作，也就是将一组数据变成堆的过程。这个过程从底部开始，（对最小堆来说）每次判断当前节点与子节点的大小，如果当前节点大于两个子节点，那么交换当前节点与子节点中较小的那个（对最大堆来说，就交换子节点较大的那个）
树的高度是 $log_2^n$
时间复杂度：O(n)，空间复杂度：O(n)
- 每层创建的复杂度为 $\frac {n}{2^{i+1}} * i$ ，其中 i 为从0（堆底部）开始的第 i 层，n 为堆中的节点数
- 时间复杂度为所有层的复杂度求和，取极限，等于n

import heapq
# 创建一个空的最小堆
minHeap = []
heapq.heapify(minHeap)

# 创建一个空的最大堆
# 由于Python中并没有内置的函数可以直接创建最大堆，所以一般我们不会直接创建一个空的最大堆。

# 创建带初始值的「堆」， 或者称为「堆化」操作，此时的「堆」为「最小堆」
heapWithValues = [3,1,2]
heapq.heapify(heapWithValues)

# 创建最大堆技巧
# Python中并没有内置的函数可以直接创建最大堆。
# 但我们可以将[每个元素*-1]，再将新元素集进行「堆化」操作。此时，堆顶元素是新的元素集的最小值，也可以转换成原始元素集的最大值。
# 示例
maxHeap = [1,2,3]
maxHeap = [-x for x in maxHeap]
heapq.heapify(maxHeap)
# 此时的maxHeap的堆顶元素是-3
# 将-3转换为原来的元素3，既可获得原来的maxHeap中最大的值是3

插入元素。时间复杂度：O(logN)，空间复杂度：O(1)

树的高度是 $log_2^n$ ，交换节点，最多交换 $log_2^n$ 次，表示从底一层层交换到顶部

# 最小堆插入元素
heapq.heappush(minHeap, 1)
# 最大堆插入元素
# 元素乘以-1的原因是我们将最小堆转换为最大堆。
heapq.heappush(maxHeap, 1*-1)

获取堆顶元素。时间复杂度：O(1)，空间复杂度：O(1)

# 最小堆获取堆顶元素，即最小值
minHeap[0]
# 最大堆获取堆顶元素，即最大值
# 元素乘以 -1 的原因是：我们之前插入元素时，将元素乘以 -1，所以在获取元素时，我们需要乘以 -1还原元素。
maxHeap[0]*-1

删除堆顶元素。时间复杂度：O(logN)，空间复杂度：O(1)

与插入元素的复杂度相同

# 最小堆删除堆顶元素
heapq.heappop(minHeap)
# 最大堆删除堆顶元素
heapq.heappop(maxHeap)

获取堆长度（也可以用来判断当前堆是否还有元素），都是O(1)
```
# 最小堆的长度
len(minHeap)
# 最大堆的长度
len(maxHeap)
```

堆的应用：

堆排序
- 利用堆的数据结构对一组无序元素进行排序。
- 最小堆排序算法：
  - 将所有元素堆化成一个最小堆
  - 取出并删除堆顶元素，并将该堆顶元素放置在存储有序元素的数据集T中
  - 此时，堆会调整成新的最小堆
  - 重复第二，三步，直到堆中没有元素
  - 此时得到的一个新的数据集T，元素升序排列
- 最大堆排序算法：类似
- 复杂度分析
  - 时间复杂度：O(nlogn)
  - 空间复杂度：O(n)
Top K 问题
- Top K 大元素，即最大的K个元素
  - 思路一：
    - 创建一个最大堆
    - 将所有元素都添加进最大堆中
    - 通过边删除边遍历方法，将堆顶元素进行删除，删除的元素保存到结果集T中
    - 重复第3步K次，直到去除最大的K个元素
    - 复杂度分析：
      - 时间复杂度：O(Klogn)
      - 空间复杂度：O(n)
  - 思路二：
    - 创建一个最小堆
    - 依次遍历数据中的元素，将K个元素加入到最小堆中
    - 判断当前遍历到的元素是否比最小堆的堆顶元素小，如果小则不加入，如果大，删除堆顶元素，将当前遍历元素添加到最小堆（每次添加进元素后，还应该考虑进行堆化，要确保添加进元素后现有的堆满足最小堆）
    - 重复上述步骤，直到遍历完全部元素
    - 此时最小堆中的K个元素就是前k个最大元素
    - 复杂度分析：
      - 时间复杂度：O(nlogK)
      - 空间复杂度：O(k)
- Top K 小元素，即最小的K个元素：遇上述类似
Top Kth 问题
- The Kth 大元素的解法：
  - 思路一：
    - 创建一个最大堆
    - 将所有元素都加入到最大堆中
    - 通过边删除边遍历的方法，将堆顶元素进行删除
    - 重复上一个步骤，直到获取第K个最大的元素
    - 复杂度分析：
      - 时间复杂度：O(Klogn)
      - 空间复杂度：O(n)
  - 思路二：
    - 创建一个最小堆
    - 依次将元素添加到最小堆中；
    - 当最小堆的元素个数已达K个时，将当前元素与堆顶元素进行比较：
      - 当前元素小于堆顶元素，跳过
      - 当前元素大于堆顶元素，删除堆顶元素，将当前元素加入到最小堆中
    - 重复上一步，直到元素全部遍历完
    - 此时最小堆中的堆顶元素（就是最小的那个）就是第K大的元素
    - 复杂度分析：
      - 时间复杂度：O(nlogk)
      - 空间复杂度：O(k)
- The Kth 小的元素解法：类似

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

核心方法：使用堆排序方法。维护一个元素个数为k的最小堆。

难点：遍历数组，将前k个元素组成最小堆，然后判断当前遍历到的元素是否比堆顶元素大，如果小则继续遍历，如果大则删除堆顶元素，然后将当前元素添加到堆中。遍历完毕后，则取出栈顶元素，就是第K大的元素。

复杂度分析：

时间复杂度：O(nlogk)，每个元素遍历一次，时间复杂度为O(n)；遍历每个元素时，一个完全二叉树变为一个最小堆需要移动替换，最多是二叉树的叶子结点变为堆顶点，树高logk，所以操作的复杂度为：O(logk)
空间复杂度：堆中元素共有k个，所以O(k)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        minHeap = list()
        heapq.heapify(minHeap)
        for num in nums:
            if i < k:
                heapq.heappush(minHeap, num)
            else:
                if num > minHeap[0]:
                    heapq.heappop(minHeap)
                    heapq.heappush(minHeap, num)
        return minHeap[0]

核心方法：使用选择排序法

时间复杂度：O(kn)

空间复杂度：O(1)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 使用选择排序的方法，只排k个。选择k次数组中的最大元素，
        # 将其交换到数组前面，然后返回数组的第k个数
        n = len(nums)
        maxIdx = 0
        for i in range(k):
            maxIdx = i
            for j in range(i+1, n):
                if nums[maxIdx] < nums[j]:
                    maxIdx = j
            tmp = nums[i]
            nums[i] = nums[maxIdx]
            nums[maxIdx] = tmp
        return nums[k-1]

剑指offer40，最小的k个数，简单

核心方法：使用堆排序，维护一个最大堆。

难点：维护一个最大堆。遍历数据，将数据中前k个元素添加到最大堆中。比较当前遍历到的数据与堆顶元素的大小，如果比堆顶元素小，则删除堆顶元素，然后当前元素添加进堆中。如果比堆顶元素大，则不加入，直到完成遍历。剩余的堆就是最小的k个数组成的。

注意：由于维护的是最大堆，push进堆前需要确保输入的元素取负号，最后返回时也要将所有元素再取负号变回原来的样子。

复杂度分析：

时间复杂度：O(nlogk)，每个元素遍历一次，时间复杂度为O(n)；遍历每个元素时，一个完全二叉树变为一个最小堆需要移动替换，最多是二叉树的叶子结点变为堆顶点，树高logk，所以操作的复杂度为：O(logk)
堆中元素共有k个，所以O(k)

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        maxheap = list()
        heapq.heapify(maxheap)
        for num in arr:
            if k > 0:
                heapq.heappush(maxheap, -1 * num)
                k -= 1
            else:
                if maxheap and num < -1 * maxheap[0]:
                    # 这里考虑到maxheap存在，是需要覆盖掉k为0的情况
                    heapq.heappop(maxheap)
                    heapq.heappush(maxheap, -1 * num)
        return [-1 * a for a in maxheap]

347，前k个高频元素，中等

核心方法：使用堆！

难点：如果传入堆中的数据是元组，那么需要确保传入的元组中[0]的位置是要在堆中排序的那个数

时间复杂度：O(nlogk)

空间复杂度：O(k)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = collections.Counter(nums)
        minHeap = list()
        heapq.heapify(minHeap)
        for key, value in freq.items():
            if k > 0:
                heapq.heappush(minHeap, (value, key))
                k -= 1
            else:
                if value > minHeap[0][0]:
                    heapq.heappop(minHeap)
                    heapq.heappush(minHeap, (value, key))
        return [pair[1] for pair in minHeap]

239，滑动窗口最大值，困难

核心方法：使用最大堆，效果不如迭代法

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 使用最大堆的方法进行处理，最大堆中存放的是元素和元素在nums中的索引
        # 首先把前nums中前k个元素加入最大堆
        maxheap = [(-1 * nums[i], i) for i in range(k)]
        heapq.heapify(maxheap)
        # 此时最大堆中的堆顶元素就是当前窗口内的最大值
        ans = [-1 * maxheap[0][0]]
        for i in range(k, len(nums)):
            # 现将新的元素，按照堆的元素格式加入堆中
            heapq.heappush(maxheap, (-1 * nums[i], i))
            # 将堆中堆顶元素去不在当前窗口内的元素全部pop掉
            while maxheap[0][1] <= i - k:
                heapq.heappop(maxheap)
            # 将当前堆顶元素加入到结果中
            ans.append(-1 * maxheap[0][0])
        return ans

692，前k个高频单词，中等

核心方法：使用最小堆。但是不能直接使用heapq进行创建堆。因为题目要求，返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

如果采取：将前k个元素依次弹入；从第k+1个元素开始，只要新的元素的频率比堆顶（最小值）大的，就弹出堆顶元素，将新元素加入堆；遍历完毕后，堆中剩余的元素就是前k个最大的元素。这种方法得到的结果是有问题的，对于两个频率相同的单词，有可能输出的顺序是原顺序反过来。

如果将所有元素的词频取反，然后依次加入最小堆，然后再依次弹出k次堆顶元素，那么就能达到效果。代码如下：

时间复杂度：$O(nlogn)$

空间复杂度：$O(n)$

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        freq = collections.Counter(words)
        minHeap = list()
        heapq.heapify(minHeap)
        for key, v in freq.items():
            heapq.heappush(minHeap, (-1 * v, key))
        res = list()
        for _ in range(k):
            res.append(heapq.heappop(minHeap)[1])
        return res

另外一种方法，直接重写富比较方法。富比较方法能够直接参与实例的比较，而实际参与比较的是实例的对象。这里不直接使用heapq的堆化操作，通过重写富比较方法对词和词频的封装。__lt__表示的小于，当加入堆中进行比较的时候，元素之间以由小到大的方式进行排列（实例对象已经封装好了）

重写的富比较方法中，定义首先确保词频最小；如果词频的大小一致，那么比较词的顺序。

时间复杂度：$O(nlogk)$

空间复杂度：$O(k)$

class Word:
    def __init__(self, word, fre):
        self.word = word
        self.fre = fre
    def __lt__(self, other):
        if self.fre != other.fre:
            return self.fre < other.fre
        return self.word > other.word

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = collections.Counter(words)
        heap = list()
        for word, fre in cnt.items():
            heapq.heappush(heap, Word(word, fre))
            if len(heap) > k:
                heapq.heappop(heap)

        heap.sort(reverse=True)
        return [x.word for x in heap]

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

堆.md

堆.md

堆

需求分析：

要点：

定义和分类

Files

堆.md

Latest commit

History

堆.md

File metadata and controls

堆

需求分析：

要点：

定义和分类