heap

id: heap  
title: 编码面试堆技巧速查表  
description: 编码面试堆学习指南，包括练习题、技巧、时间复杂度及推荐资源  
keywords:  
  [堆编码面试学习指南,  
   堆编码面试技巧,  
   堆练习题,  
   堆实用技巧,  
   堆时间复杂度,  
   堆推荐学习资源]  
sidebar_label: 堆  
toc_max_heading_level: 2​

引言

堆是一种特殊的基于树的数据结构，它是一种满足堆性质的完全二叉树。

• 最大堆——在最大堆中，一个节点的值必须是其整个子树中所有节点值中的最大值。这一性质对树中所有节点都需递归地成立。
• 最小堆——在最小堆中，一个节点的值必须是其整个子树中所有节点值中的最小值。这一性质对树中所有节点都需递归地成立。

在算法面试的背景下，堆与优先队列可以视为同一种数据结构。当需要反复移除优先级最高的（或最低的）对象，或者插入操作需要穿插着根节点的移除时，堆是一种非常有用的数据结构。

学习资源

• 爱上堆, basecs
• 用堆排序搞定一切, basecs
• 堆, 耶鲁大学 James Aspnes

实现方式

时间复杂度

技巧

关于k的说明

如果题目中提到寻找前 k 大或前 k 小的元素，通常意味着可以用堆来解决这个问题，比如在前 K 个高频元素中。

如果你需要找出前 k 大的元素，可以使用大小为 k 的最小堆。遍历每个元素，将其压入堆中（对于 Python heapq，压入前需要先取反以找到最大值）。每当堆的大小超过 k 时，移除最小元素，这样就能保证你得到的是前 k 大的元素。

必备题目

这些是备考本主题时必须练习的题目。

• 合并 K 个有序链表
• 到原点距离最短的 K 个点

推荐练习题目

这些是在你学完本主题并练习过必备题目后推荐的题目。

• 前 K 个高频元素
• 从数据流中查找中位数

推荐课程

import AlgorithmCourses from '../_courses/AlgorithmCourses.md'

免责声明：
本文档采用基于机器的 AI 翻译服务进行翻译。尽管我们力求准确，但请注意，自动翻译可能存在错误或不准确之处。应以原文语言版本的文档作为权威依据。如需获取关键信息，建议使用专业的人工翻译。对于因使用本翻译而产生的任何误解或误读，我们概不负责。