java代码如何实现堆结构及堆排序功能 java代码堆数据结构的基础编写教程​

<blockquote>堆结构在Java中通过数组模拟树形结构，核心是维护堆属性的上浮和下沉操作，堆排序利用大顶堆进行原地排序，时间复杂度稳定为O(n log n)，适用于优先级队列和Top K问题。</blockquote> <p><img src=”https://img.php.cn/upload/article/001/503/042/175517280397743.jpeg” alt=”java代码如何实现堆结构及堆排序功能 java代码堆数据结构的基础编写教程​”></p> <p>在Java中实现堆结构和堆排序，核心在于利用数组模拟树形结构，并精心维护其“堆属性”（父节点总是大于或小于其子节点）。堆排序则是在此基础上，通过反复取出最大/最小元素来达到排序目的。说实话，这玩意儿初看有点绕，但一旦你理解了数组索引和树节点的关系，就豁然开朗了。</p> <h3>解决方案</h3> <p>要实现一个堆结构，我们通常会选择用数组来承载。一个Max-Heap（大顶堆）的核心是每个父节点的值都大于或等于其子节点。堆排序，顾名思义，就是利用这种堆结构来完成数组的排序。</p> <p><strong>1. 堆结构（Max-Heap）的实现</strong></p> <p>我们可以定义一个<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>MaxHeap</pre><div class=”contentsignin”></div></div>类，用<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>ArrayList</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>或者固定大小的数组来存储元素，这样更灵活些。这里我倾向于用<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>ArrayList</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>，因为它动态扩容省心。</p> <p><span>立即学习</span>“<a href=”https://pan.quark.cn/s/c1c2c2ed740f” style=”text-decoration: underline !important; color: blue; font-weight: bolder;” rel=”nofollow” target=”_blank”>Java免费学习笔记（深入）</a>”；</p><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=’brush:java;toolbar:false;’>import java.util.ArrayList; import java.util.List; import java.util.NoSuchElementException; public class MaxHeap { private List<Integer> heap; public MaxHeap() { this.heap = new ArrayList<>(); } // 插入元素 public void insert(int value) { heap.add(value); heapifyUp(heap.size() – 1); // 新元素可能破坏堆属性，需要上浮 } // 提取最大元素（堆顶） public int extractMax() { if (isEmpty()) { throw new NoSuchElementException("Heap is empty."); } int max = heap.get(0); int lastElement = heap.remove(heap.size() – 1); // 移除最后一个元素 if (!isEmpty()) { heap.set(0, lastElement); // 将最后一个元素放到堆顶 heapifyDown(0); // 新堆顶可能破坏堆属性，需要下沉 } return max; } // 查看最大元素（不移除） public int peekMax() { if (isEmpty()) { throw new NoSuchElementException("Heap is empty."); } return heap.get(0); } public boolean isEmpty() { return heap.isEmpty(); } public int size() { return heap.size(); } // 元素上浮操作：当新元素插入或元素值增大时，将其向上移动以维护堆属性 private void heapifyUp(int index) { int parentIndex = (index – 1) / 2; // 计算父节点索引 while (index > 0 && heap.get(index) > heap.get(parentIndex)) { swap(index, parentIndex); index = parentIndex; parentIndex = (index – 1) / 2; } } // 元素下沉操作：当堆顶元素被移除或元素值减小时，将其向下移动以维护堆属性 private void heapifyDown(int index) { int leftChildIndex = 2 * index + 1; int rightChildIndex = 2 * index + 2; int largestIndex = index; // 假设当前节点最大 // 检查左子节点 if (leftChildIndex < heap.size() && heap.get(leftChildIndex) > heap.get(largestIndex)) { largestIndex = leftChildIndex; } // 检查右子节点 if (rightChildIndex < heap.size() && heap.get(rightChildIndex) > heap.get(largestIndex)) { largestIndex = rightChildIndex; } // 如果最大值不是当前节点，则交换并继续下沉 if (largestIndex != index) { swap(index, largestIndex); heapifyDown(largestIndex); } } // 交换两个位置的元素 private void swap(int i, int j) { int temp = heap.get(i); heap.set(i, heap.get(j)); heap.set(j, temp); } // 用于调试，打印堆内容 public void printHeap() { System.out.println(heap.toString()); } }</pre><div class=”contentsignin”></div></div><p><strong>2. 堆排序功能的实现</strong></p> <p>堆排序通常是原地排序，直接在原数组上操作。它分为两个主要阶段：</p> <ul> <li> <strong>建堆（Build Heap）</strong>：将一个无序数组构建成一个大顶堆（或小顶堆）。这个过程从最后一个非叶子节点开始，依次向上对其进行下沉操作。</li> <li> <strong>排序（Sort）</strong>：重复地将堆顶元素（最大值）与堆的最后一个元素交换，然后将剩余的元素重新调整为堆。每次交换后，堆的大小减一。</li> </ul><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=’brush:java;toolbar:false;’>public class HeapSort { // 堆排序主方法 public static void sort(int[] arr) { int n = arr.length; // 1. 构建大顶堆（从最后一个非叶子节点开始向上heapify） // 最后一个非叶子节点的索引是 (n/2 – 1) for (int i = n / 2 – 1; i >= 0; i–) { heapify(arr, n, i); } // 2. 逐个提取元素进行排序 for (int i = n – 1; i > 0; i–) { // 将当前最大元素（堆顶）与当前堆的最后一个元素交换 swap(arr, 0, i); // 对剩余的元素（不包括已排序的元素）重新进行堆化 heapify(arr, i, 0); // 注意这里的n变成了i，表示堆的有效大小 } } // 维护堆属性的下沉操作（与MaxHeap中的heapifyDown类似，但操作的是数组） private static void heapify(int[] arr, int n, int i) { int largest = i; // 初始化最大元素为根节点 int left = 2 * i + 1; // 左子节点 int right = 2 * i + 2; // 右子节点 // 如果左子节点存在且大于当前最大元素 if (left < n && arr[left] > arr[largest]) { largest = left; } // 如果右子节点存在且大于当前最大元素 if (right < n && arr[right] > arr[largest]) { largest = right; } // 如果最大元素不是根节点，则交换并递归下沉 if (largest != i) { swap(arr, i, largest); heapify(arr, n, largest); } } // 交换数组中两个元素的位置 private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { // 测试MaxHeap System.out.println("— MaxHeap 示例 —"); MaxHeap maxHeap = new MaxHeap(); maxHeap.insert(3); maxHeap.insert(2); maxHeap.insert(15); maxHeap.insert(5); maxHeap.insert(4); maxHeap.insert(45); maxHeap.printHeap(); // 应该看到一个符合大顶堆特性的数组表示 System.out.println("提取最大值: " + maxHeap.extractMax()); // 45 maxHeap.printHeap(); System.out.println("提取最大值: " + maxHeap.extractMax()); // 15 maxHeap.printHeap(); // 测试HeapSort System.out.println("n— 堆排序示例 —"); int[] data = {12, 11, 13, 5, 6, 7}; System.out.println("原始数组: " + java.util.Arrays.toString(data)); HeapSort.sort(data); System.out.println("排序后数组: " + java.util.Arrays.toString(data)); int[] data2 = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; System.out.println("原始数组2: " + java.util.Arrays.toString(data2)); HeapSort.sort(data2); System.out.println("排序后数组2: " + java.util.Arrays.toString(data2)); } }</pre><div class=”contentsignin”></div></div><h3>堆结构在Java中为何如此重要？其优缺点与适用场景分析</h3> <p>说实话，堆这个数据结构在计算机科学里地位挺特殊的，它既不像链表那么直观，也不像哈希表那样“快得离谱”，但它在某些场景下就是无可替代。在Java里，最常见的应用就是<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>java.util.PriorityQueue</pre><div class=”contentsignin”></div></div>，它底层就是用堆实现的。</p> <p><strong>优点：</strong></p> <ul> <li> <strong>高效的优先级队列实现：</strong> 这是堆最核心的价值。无论是插入元素还是取出最高（或最低）优先级的元素，时间复杂度都是O(log n)。这比数组或链表实现的优先级队列效率高得多。</li> <li> <strong>稳定的时间复杂度：</strong> 堆排序在最坏、平均、最好情况下的时间复杂度都是O(n log n)，这一点比快速排序（最坏O(n^2)）要稳定得多。对于需要稳定性能保证的场景，堆排序是个不错的选择。</li> <li> <strong>原地排序（对于堆排序）：</strong> 堆排序只需要常数级的额外空间，因为它直接在原数组上进行操作。这对于内存受限的环境来说是个大优点。</li> <li> <strong>查找Kth最大/最小元素：</strong> 堆可以非常高效地找到数组中第K个最大或最小的元素，时间复杂度通常是O(n log k)。</li> </ul> <p><strong>缺点：</strong></p> <ul> <li> <strong>不稳定排序：</strong> 堆排序是一种不稳定的排序算法，这意味着相同值的元素的相对顺序在排序后可能会改变。如果你对元素的原始顺序有要求，这可能会是个问题。</li> <li> <strong>缓存局部性差：</strong> 堆在数组中的表示是跳跃的，父子节点在内存中不一定是连续的。这会导致CPU缓存命中率相对较低，在实际运行中可能不如归并排序或快速排序表现好，尽管它们的理论时间复杂度相同。</li> <li> <strong>不直观：</strong> 对于初学者来说，理解堆的数组表示和上浮/下沉操作确实需要一点时间去适应。</li> </ul> <p><strong>适用场景：</strong></p> <ul> <li> <strong>优先级队列：</strong> 任务调度（<a >操作系统</a>、网络路由器）、事件模拟、Dijkstra最短路径算法、Prim最小生成树算法等。</li> <li> <strong>Top K 问题：</strong> 从海量数据中找出最大的K个元素，或者最小的K个元素。比如，找出访问量最高的100个网页，或者销售额最高的50个商品。</li> <li> <strong>外部排序：</strong> 当数据量大到内存无法一次性加载时，可以利用堆进行分块排序。</li> <li> <strong>在线算法：</strong> 实时处理数据流，比如实时中位数计算。</li> </ul> <p>总的来说，堆虽然有些“怪脾气”，但它在需要高效处理“最大/最小”或“优先级”这类问题的场景中，简直就是个MVP。</p> <h3>深入剖析Java堆操作核心：上浮（Swim）与下沉（Sink）机制详解</h3> <p>堆操作的核心，毫无疑问就是那两个听起来有点玄乎的“上浮”（Swim，有时也叫<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>heapifyUp</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>）和“下沉”（Sink，或<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>heapifyDown</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>）。这俩是维护堆属性的基石，所有的插入、删除操作都离不开它们。我个人觉得，理解了这两个操作，就等于抓住了堆的灵魂。</p> <p><strong>1. 上浮（Swim / <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>heapifyUp</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>）</strong></p> <p>想象一下，你往一个已经整理好的大顶堆里塞了一个新元素。这个新元素，我们暂时把它放在数组的最后面。但问题来了，它可能比它的父节点还大！这就破坏了堆的“父大子小”的规矩。怎么办？</p> <p>上浮操作就是来解决这个问题的。它会不断地把这个“不守规矩”的新元素和它的父节点进行比较。如果新元素比父节点大，那就交换它们的位置。然后，新元素就“上浮”了一层，它会继续和新的父节点比较，直到它找到了一个比它大的父节点（或者它自己成了堆顶），这样堆的属性就恢复了。</p> <ul> <li> <strong>逻辑：</strong> 从当前节点开始，与其父节点比较。如果当前节点值大于父节点值，则交换两者位置，然后将当前节点索引更新为原父节点索引，继续向上比较，直到根节点或不再大于父节点。</li> <li> <strong>时间复杂度：</strong> O(log n)，因为每次操作都向上移动一层，而堆的高度是log n。</li> </ul> <p><strong>2. 下沉（Sink / <div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>heapifyDown</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>）</strong></p> <p>下沉操作通常发生在两种情况：</p> <ul> <li>你从堆顶取走了最大（或最小）的元素后，为了填补空缺，把堆里最后一个元素挪到了堆顶。</li> <li>某个元素的值变小了，它可能不再比它的子节点大。</li> </ul> <p>无论是哪种情况，堆顶（或某个节点）都可能不再符合堆的属性。下沉操作就是让这个“不守规矩”的元素向下移动，直到它找到一个合适的位置。它会比较自己和它的两个子节点，找出其中最大的那个（对于大顶堆）。如果它自己不是最大的，就和最大的那个子节点交换位置，然后继续向下沉，直到它比两个子节点都大（或者它已经到了叶子节点）。</p> <ul> <li> <strong>逻辑：</strong> 从当前节点开始，与其左、右子节点比较。找出当前节点、左子节点、右子节点中值最大的那个。如果最大值不是当前节点，则将当前节点与最大值的子节点交换，然后将当前节点索引更新为交换后的子节点索引，继续向下比较，直到叶子节点或不再小于子节点。</li> <li> <strong>时间复杂度：</strong> O(log n)，原理同上浮，每次操作向下移动一层。</li> </ul> <p>这两个操作就像是堆的“自愈”机制。无论你往堆里加什么，或者从堆里拿走什么，它们都能确保堆的结构始终保持着那种有序性。理解它们是理解堆性能的关键，也是自己手写堆代码时最容易出错但也最能体现功力的地方。</p> <h3>Java实现堆结构时常见的挑战与优化策略</h3> <p>手写堆结构和堆排序，虽然理论上清晰，但实际敲代码时总会遇到些“坑”。这就像你看着地图觉得路很好走，真走起来才发现有小石子绊脚。</p> <p><strong>常见的挑战：</strong></p> <ul> <li> <strong>索引计算错误：</strong> 这是最常见的，尤其是对于0-based数组（Java默认）和1-based数组（一些理论教材）之间的转换。<ul> <li>父节点：<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>(i – 1) / 2</pre><div class=”contentsignin”></div></div></li> <li>左子节点：<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>2 * i + 1</pre><div class=”contentsignin”></div></div></li> <li>右子节点：<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>2 * i + 2</pre><div class=”contentsignin”></div></div> 稍微写错一个数字，整个堆可能就乱了。</li> </ul> </li> <li> <strong>边界条件处理：</strong> 比如堆为空时<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>extractMax</pre><div class=”contentsignin”></div></div>、<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>peekMax</pre><div class=”contentsignin”></div></div>的异常处理；在<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>heapifyUp</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>和<div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>heapifyDown</pre><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div><div class=”contentsignin”></div></div>中，判断子节点或父节点是否存在（<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>index > 0</pre><div class=”contentsignin”></div></div>或<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>childIndex < heap.size()</pre><div class=”contentsignin”></div></div>）。这些细节处理不好，就容易出现<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>IndexOutOfBoundsException</pre><div class=”contentsignin”></div></div>。</li> <li> <strong>大顶堆/小顶堆的判断逻辑：</strong> 到底是<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>></pre><div class=”contentsignin”></div></div>还是<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”><</pre><div class=”contentsignin”></div></div>？如果混淆了，你可能把一个大顶堆写成了小顶堆，或者反之。对于排序，大顶堆通常用于升序排序（每次取最大），小顶堆用于降序排序（每次取最小）。</li> <li> <strong>原地排序的理解：</strong> 堆排序的第二阶段，每次把堆顶元素放到数组末尾已排序区域时，要记得更新堆的有效大小（<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>n</pre><div class=”contentsignin”></div></div>或<div class=”code” style=”position:relative; padding:0px; margin:0px;”><pre class=”brush:php;toolbar:false”>i</pre><div class=”contentsignin”></div></div>参数），否则会把已排序的元素又</li> </ul>