Reading

堆（大顶堆&小顶堆）

Feb 25, 2026
2148 views
Algorithm
#Algorithm

实现

方式一：使用 heapq 标准库

这是 Python 最快、最节省内存的方式，因为 heapq底层是用 C 语言实现的。

小顶堆 (Min Heap)

Python 的 heapq默认就是小顶堆。

import heapq

# 初始化
min_heap = []

# 添加元素 O(log N)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 8)

# 查看堆顶 O(1)
print(min_heap[0])  # 输出: 2

# 弹出堆顶 O(log N)
pop_val = heapq.heappop(min_heap)
print(pop_val)      # 输出: 2
print(min_heap)     # 输出: [5, 8] (注意：堆内部不一定有序，但堆顶一定是最小的)

# 将已有的列表转化为堆 O(N)
nums = [5, 7, 1, 3]
heapq.heapify(nums)
print(nums)         # 输出: [1, 3, 5, 7] (类似这样的堆结构)

大顶堆 (Max Heap)

Python 没有直接的大顶堆库。标准做法是将数值取负 (-x) 存入小顶堆。取出时再取负还原。

import heapq

class MaxHeap:
    def __init__(self):
        self.heap = []
    
    def push(self, val):
        # 存入负数
        heapq.heappush(self.heap, -val)
        
    def pop(self):
        # 取出后取反还原
        return -heapq.heappop(self.heap)
        
    def peek(self):
        return -self.heap[0]
        
    def __len__(self):
        return len(self.heap)

# 使用
max_h = MaxHeap()
max_h.push(10)
max_h.push(5)
max_h.push(20)

print(max_h.peek()) # 输出: 20
print(max_h.pop())  # 输出: 20
print(max_h.pop())  # 输出: 10

方式二：手写实现 (原理学习)

如果你需要理解堆的底层逻辑（上浮 sift_up和 下沉 sift_down），可以参考以下代码。这里以 大顶堆 为例。

数组索引规律：

  • 当前节点：\(i\)
  • 父节点：\((i - 1) // 2\)
  • 左孩子：\(2 \times i + 1\)
  • 右孩子：\(2 \times i + 2\)
class ManualMaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        """插入元素：先放到末尾，然后上浮"""
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        """弹出堆顶：将末尾元素换到堆顶，删除末尾，然后堆顶下沉"""
        if not self.heap:
            raise IndexError("pop from empty heap")
        
        # 交换堆顶和最后一个元素
        self._swap(0, len(self.heap) - 1)
        # 弹出最大值
        val = self.heap.pop()
        # 让新的堆顶下沉到合适位置
        self._sift_down(0)
        return val

    def _sift_up(self, index):
        """上浮：如果比父节点大，就交换"""
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[index] > self.heap[parent]:
                self._swap(index, parent)
                index = parent
            else:
                break

    def _sift_down(self, index):
        """下沉：如果比子节点小，就和较大的子节点交换"""
        n = len(self.heap)
        while True:
            left = 2 * index + 1
            right = 2 * index + 2
            largest = index

            # 寻找 自己、左孩子、右孩子 中最大的那个
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            
            # 如果最大的不是自己，说明需要下沉
            if largest != index:
                self._swap(index, largest)
                index = largest
            else:
                break

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

# 测试
mh = ManualMaxHeap()
mh.push(10)
mh.push(30)
mh.push(20)
print(mh.pop()) # 30
print(mh.pop()) # 20
print(mh.pop()) # 10

88. 合并两个（K个）有序数组

题目

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted
array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is equal to m + n) to hold
additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3


Output: [1,2,2,3,5,6]

Constraints:

  • \(10^9\) <= nums1[i], nums2[i] <= \(10^9\)
  • nums1.length == m + n
  • nums2.length == n

题目大意

合并两个已经有序的数组，结果放在第一个数组中，第一个数组假设空间足够大。要求算法时间复杂度
足够低。

解题

为了不大量移动元素，就要从2个数组⻓度之和的最后一个位置开始，依次选取两个数组中大的数，从第一个数组的尾巴开始往头放，只要循环一次以后，就生成了合并以后的数组了。

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        # two get pointers for nums1 and nums2
        p1 = m - 1
        p2 = n - 1
        # set pointer for nums1
        p = m + n - 1

        # while there are still elements to compare
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] =  nums1[p1]
                p1 -= 1
            p -= 1

        # add missing elements from nums2
        nums1[:p2 + 1] = nums2[:p2 + 1]

合并K个

给定\(k\)个有序数组，每个数组有\(n\)个元素，想把这些数组合并成一个有序数组

可以利用最小堆完成，时间复杂度是\(O(nklogk)\)，具体过程如下：

  1. 创建一个大小为\(nk\)的数组保存最后的结果
  2. 创建一个大小为\(k\)的最小堆，堆中元素为\(k\)个数组中的每个数组的第一个元素, 重复下列步骤\(nk\)次：
    1. 每次从堆中取出最小元素（堆顶元素），并将其存入输出数组中。
    2. 用堆顶元素所在数组的下一元素将堆顶元素替换掉，如果数组中元素被取光了，将堆顶元素替换为无穷大。
    3. 每次替换堆顶元素后，重新调整堆

初始化最小堆的时间复杂度\(O(k)\)，总共有\(kn\)次循环，每次循环调整最小堆的时间复杂度是\(O(logk)\)，所以总的时间复杂度是\(O(knlogk)\)

import sys

class HeapNode:
    def __init__(self,x,y=0,z=0):
        self.value=x
        self.i=y
        self.j=z


def Min_Heap(heap):#构造一个堆，将堆中所有数据重新排序
    HeapSize = len(heap)#将堆的长度单独拿出来方便
    for i in range((HeapSize -2)//2,-1,-1):#从后往前出数
        Min_Heapify(heap,i)


def Min_Heapify(heap,root):
    heapsize=len(heap)
    MIN=root
    left=2*root+1
    right=left+1
    if left<heapsize and heap[MIN].value>heap[left].value:
        MIN=left
    if right <heapsize and heap[MIN].value>heap[right].value:
        MIN=right
    if MIN!=root:
        heap[MIN], heap[root] = heap[root], heap[MIN]
        Min_Heapify(heap, MIN)

def MergeKArray(nums,n):
    # 合并k个有序数组，每个数组长度都为k
    knums=[]
    output=[]
    for i in range(len(nums)):
        subnums=nums[i]
        knums.append(HeapNode(subnums[0],i,1))
   　#k个元素初始化最小堆
		Min_Heap(knums)

    for i in range(len(nums)*n):
        # 取堆顶，存结果
        root=knums[0]
        output.append(root.value)
        #替换堆顶
        if root.j<n:
            root.value=nums[root.i][root.j]
            root.j+=1
        else:
            root.value=sys.maxsize
        knums[0]=root
        Min_Heapify(knums,0)
    return output


knums=[[1,2,3],[1,3,6],[4,5,8]]
print(MergeKArray(knums,3))