当前位置：首页 > ai >正文

数据结构07（Java）-- （堆，大根堆,堆排序）

ai 2025/8/27 7:59:53

前言

本文为本小白🤯学习数据结构的笔记，将以算法题为导向，向大家更清晰的介绍数据结构相关知识（算法题都出自🙌B站马士兵教育——左老师的课程，讲的很好，对于想入门刷题的人很有帮助👍）

上面写完了归并排序，快速排序，排序它本身整个算法并没有什么，重要的是他的算法，它怎么提升时间复杂度，以及这种思想的应用，这是我们更要去关注的。下面来看一个新的排序——堆排序。

下面来介绍一下数据结构中的“堆”（Heap）。

1.堆 (Heap) 概述

堆结构就是用数组实现的完全二叉树结构

堆是一棵完全二叉树。这意味着除了最后一层，其他层都被完全填满，且最后一层的节点都尽可能地靠左排列。
堆的数组表示：由于堆是完全二叉树，可以用数组 heap[0…n-1] 来存储（通常索引从 0 开始）：
- 根节点：heap[0]
- 节点 i 的左子节点：heap[2*i + 1]
- 节点 i 的右子节点：heap[2*i + 2]
- 节点 i 的父节点：heap[(i-1) / 2] (整数除法)

这种表示法非常节省空间，且父子节点的访问是 O(1) 的。

        索引: 0 (值: 50)/                  \索引: 1 (值: 30)     索引: 2 (值: 40)/        \           /        \
索引:3    索引:4     索引:5     索引:6
(值:20)   (值:10)   (值:35)   (值:25)

数组索引:   0     1     2     3     4     5     6+-----+-----+-----+-----+-----+-----+-----+
数组值:   | 50  | 30  | 40  | 20  | 10  | 35  | 25  |+-----+-----+-----+-----+-----+-----+-----+

2.堆主要有两种类型：

大根堆 (Max Heap)：对于树中的任意节点，其值大于或等于其子节点的值。因此，根节点（堆顶）是整个堆中最大的元素。

实现大根堆：

package DiGui;public class Dui {public static void heapInsert(int [] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}public static void swap(int [] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}
}

大根堆应用: 去掉堆中的最大值，其结构仍保持大根堆

实现思路：
1.找到堆中最大值：肯定是数组中，下标为0的数，这个很简单。
2.去掉最大值保持大根堆：将数组中下标最大的数，赋值给下标为0位置，在用heapify方法往下调整堆结构。

（heapify方法）：

//构建堆，index：构建堆结构下表，一下全是堆结构，heapSize：整个arr数组长度防止越界
public static void heapify(int [] arr. int index, int heapSize){//index 左孩子int left = index * 2 + 1;while (left < heapSize) {//index右孩子，与左孩子比较，取最大值下标int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;//判断arr[largest] 与 arr[index] 大小取最大值下标largest = arr[largest] > arr[index] ? largest : index;if (largest == index) {break;}swap( arr, largest, index);index = largest;}
}public static void swap(int [] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];

时间复杂度O(logN)

最小堆 (Min Heap)：对于树中的任意节点，其值小于或等于其子节点的值。因此，根节点（堆顶）是整个堆中最小的元素。

堆排序

先来看代码吧：

package DiGui;public class Dui {public static void heapSort(int [] arr) {if (arr == null || arr.length < 2) {return;}//先把整个数组变成大根堆for (int i = 0; i < arr.length; i++) {heapInsert(arr, i);}//再使整个大根堆有序int heapSize = arr.length;//将数组中最后一个数跟第一个数交换，再heapify，之后一个一个交换，使其完全有序swap(arr, 0, --heapSize);while (heapSize > 0) {heapify(arr, 0, heapSize);swap(arr, 0, --heapSize);}}//public static void heapInsert(int [] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}public static void heapify(int [] arr, int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;largest = arr[largest] > arr[index] ? largest : index;if (largest == index) {break;}swap(arr, largest, index);index = largest;}}public static void swap(int [] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}
}