Java必须掌握的二叉堆知识点（含面试大厂题含源码）

二叉堆是一种常用的优先队列数据结构，广泛应用于各种场景，比如任务调度、带权图的最短路径算法（如Dijkstra算法）等。在Java面试中，了解二叉堆的基本概念、实现方式和操作是非常重要的。下面是一些关于二叉堆的关键知识点，这些内容会帮助你在面试大厂时更好地展示你的技术实力。

二叉堆的定义

二叉堆是一种完全二叉树，它可以分为两种类型：

• 最小堆：父节点的值总是小于或等于其任意子节点的值。
• 最大堆：父节点的值总是大于或等于其任意子节点的值。

二叉堆的性质

• 结构性质：二叉堆是一种完全二叉树，这意味着除了最后一层外，每一层都被完全填满，并且最后一层的所有节点都尽可能地集中在左边。
• 堆序性质：在最小堆中，每个节点的值都小于或等于其子节点的值；在最大堆中，每个节点的值都大于或等于其子节点的值。

二叉堆的存储

二叉堆通常使用数组来存储，不需要使用节点指针。给定一个索引为i的节点：

• 它的父节点的索引是 (i-1)/2（对于i>0）。
• 它的左子节点的索引是 2*i + 1。
• 它的右子节点的索引是 2*i + 2。

二叉堆的基本操作

• 插入操作：新元素被加到堆的末尾，然后向上调整（上浮）以恢复堆的性质。
• 删除操作（最小堆为例）：删除堆顶元素，通常是堆中最小的元素。然后将最后一个元素移动到堆顶，之后向下调整（下沉）以恢复堆的性质。

Java中的二叉堆实现

虽然Java标准库中没有直接提供二叉堆的实现，但是PriorityQueue类提供了基于优先队列的实现，底层就是使用二叉堆（默认是最小堆）实现的。PriorityQueue提供了如下几个关键方法：

• add(E e) / offer(E e)：将指定的元素插入此优先队列。
• remove() / poll()：检索并删除此队列的头部，即最小元素。
• element() / peek()：检索但不删除此队列的头部，即最小元素。

二叉堆的应用

• 优先队列的实现：使用二叉堆可以高效地实现优先队列，支持插入和删除最小元素的操作。
• 堆排序：通过构建最大堆（或最小堆），可以实现堆排序算法，这是一种原地排序算法，但不是稳定的。
• 图算法中的应用：在很多图算法中，如Dijkstra和Prim算法，优先队列（通常通过二叉堆实现）被用来高效地选择下一个要处理的节点。

掌握这些二叉堆的基础知识点对于Java面试是非常有帮助的，尤其是当你被要求手动实现数据结构或解决与之相关的算法问题时。在准备面试时，确保你理解这些概念，并且能够在需要时快速实现它们。下面是三道常见的面试题目，它们涵盖了二叉树、字符串处理以及动态规划等不同的领域，每个题目都附上了Java的实现代码。

题目1：验证二叉搜索树（Binary Search Tree, BST）

问题描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

• 节点的左子树只包含小于当前节点的数。
• 节点的右子树只包含大于当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

Java解答：

public class ValidateBinarySearchTree {public boolean isValidBST(TreeNode root) {return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean validate(TreeNode node, long min, long max) {if (node == null) return true;if (node.val <= min || node.val >= max) return false;return validate(node.left, min, node.val) && validate(node.right, node.val, max);}public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}
}

题目2：最长回文子串

问题描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s

的最大长度为 1000。

示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

Java解答：

public class LongestPalindromicSubstring {public String longestPalindrome(String s) {if (s == null || s.length() < 1) return "";int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i + 1);int len = Math.max(len1, len2);if (len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substring(start, end + 1);}private int expandAroundCenter(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}return right - left - 1;}
}

题目3：爬楼梯

问题描述：假设你正在爬楼梯。需要 n 步你才能到达顶部。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到顶部呢？

注意：给定 n 是一个正整数。

示例：

输入： 2
输出： 2
解释： 有两种方法可以爬到顶部。
1.  1 步 + 1 步
2.  2 步

Java解答：

public class ClimbingStairs {public int climbStairs(int n) {if (n == 1) return 1;int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

这些题目从基本的数据结构到算法思想都有所涵盖，是面试中非常典型的题目。掌握这些题目的解法不仅能帮助你在面试中脱颖而出，同时也能提升你解决实际问题的能力。在准备面试时，理解这些问题的核心思想和解决策略是非常重要的。