基础堆排序（Java 实例代码）

秒速五厘米 2023-10-14 15:52 34阅读 0赞

**目录**

基础堆排序

一、概念及其介绍

二、适用说明

三、过程图示

四、Java 实例代码

src/runoob/heap/Heapify.java 文件代码：

--------------------

## 基础堆排序 ##

#### 一、概念及其介绍 ####

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆是一个近似 完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

#### 二、适用说明 ####

我们之前构造堆的过程是一个个数据调用 insert 方法使用 shift up 逐个插入到堆中，这个算法的时候时间复杂度是 O(nlogn)，本小节介绍的一种构造堆排序的过程，称为 **Heapify**，算法时间复杂度为 **O(n)**。

#### 三、过程图示 ####

完全二叉树有个重要性质，对于第一个非叶子节点的索引是 **n/2** 取整数得到的索引值，其中 **n** 是元素个数(前提是数组索引从 1 开始计算)。

![8533aeaabb8bcf09d2f2cd103cd9ff0e.png][]

索引 5 位置是第一个非叶子节点，我们从它开始逐一向前分别把每个元素作为根节点进行 shift down 操作满足最大堆的性质。

索引 5 位置进行 shift down 操作后，22 和 62 交换位置。

![5e791e13029e315ffdf601d7dac7837f.png][]

对索引 4 元素进行 shift down 操作

![78f5380da0c82c652b1bc821a8b0236e.png][]

对索引 3 元素进行 shift down 操作

![d88f077f5f376a8aeaf89f450e7d57ff.png][]

对索引 2 元素进行 shift down 操作

![61f8df73255048aae76de8b24454c38e.png][]

最后对根节点进行 shift down 操作，整个堆排序过程就完成了。

![dc779b8bcc78fd27af078d7b2f4d7819.png][]

#### 四、Java 实例代码 ####

**源码包下载：**[Download![icon-default.png_t_N6B9][]https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-Heapify.zip][Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-Heapify.zip]

### src/runoob/heap/Heapify.java 文件代码： ###

package runoob.heap;  
  
import runoob.sort.SortTestHelper;  
  
/\*\*  
\* 用heapify进行堆排序  
\*/  
public class Heapify<T extends Comparable> \{  
  
protected T\[\] data;  
protected int count;  
protected int capacity;  
  
// 构造函数, 通过一个给定数组创建一个最大堆  
// 该构造堆的过程, 时间复杂度为O(n)  
public Heapify(T arr\[\])\{  
  
int n = arr.length;  
  
data = (T\[\])new Comparable\[n+1\];  
capacity = n;  
  
for( int i = 0 ; i < n ; i ++ )  
data\[i+1\] = arr\[i\];  
count = n;  
//从第一个不是叶子节点的元素开始  
for( int i = count/2 ; i >= 1 ; i -- )  
shiftDown(i);  
\}  
// 返回堆中的元素个数  
public int size()\{  
return count;  
\}  
// 返回一个布尔值, 表示堆中是否为空  
public boolean isEmpty()\{  
return count == 0;  
\}  
// 像最大堆中插入一个新的元素 item  
public void insert(T item)\{  
assert count + 1 <= capacity;  
data\[count+1\] = item;  
count ++;  
shiftUp(count);  
\}  
// 从最大堆中取出堆顶元素, 即堆中所存储的最大数据  
public T extractMax()\{  
assert count > 0;  
T ret = data\[1\];  
swap( 1 , count );  
count --;  
shiftDown(1);  
return ret;  
\}  
// 获取最大堆中的堆顶元素  
public T getMax()\{  
assert( count > 0 );  
return data\[1\];  
\}  
  
  
// 交换堆中索引为i和j的两个元素  
private void swap(int i, int j)\{  
T t = data\[i\];  
data\[i\] = data\[j\];  
data\[j\] = t;  
\}  
  
//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
//\* 最大堆核心辅助函数  
//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
private void shiftUp(int k)\{  
  
while( k > 1 && data\[k/2\].compareTo(data\[k\]) < 0 )\{  
swap(k, k/2);  
k /= 2;  
\}  
\}  
  
private void shiftDown(int k)\{  
  
while( 2\*k <= count )\{  
int j = 2\*k; // 在此轮循环中,data\[k\]和data\[j\]交换位置  
if( j+1 <= count && data\[j+1\].compareTo(data\[j\]) > 0 )  
j ++;  
// data\[j\] 是 data\[2\*k\]和data\[2\*k+1\]中的最大值  
  
if( data\[k\].compareTo(data\[j\]) >= 0 ) break;  
swap(k, j);  
k = j;  
\}  
\}  
  
// 测试 heapify  
public static void main(String\[\] args) \{  
int N = 100;  
Integer\[\] arr = SortTestHelper.generateRandomArray(N, 0, 100000);  
Heapify<Integer> heapify = new Heapify<Integer>(arr);  
// 将heapify中的数据逐渐使用extractMax取出来  
// 取出来的顺序应该是按照从大到小的顺序取出来的  
for( int i = 0 ; i < N ; i ++ )\{  
arr\[i\] = heapify.extractMax();  
System.out.print(arr\[i\] + " ");  
\}  
  
// 确保arr数组是从大到小排列的  
for( int i = 1 ; i < N ; i ++ )  
assert arr\[i-1\] >= arr\[i\];  
\}  
\}

[8533aeaabb8bcf09d2f2cd103cd9ff0e.png]: https://img-blog.csdnimg.cn/img_convert/8533aeaabb8bcf09d2f2cd103cd9ff0e.png
[5e791e13029e315ffdf601d7dac7837f.png]: https://img-blog.csdnimg.cn/img_convert/5e791e13029e315ffdf601d7dac7837f.png
[78f5380da0c82c652b1bc821a8b0236e.png]: https://img-blog.csdnimg.cn/img_convert/78f5380da0c82c652b1bc821a8b0236e.png
[d88f077f5f376a8aeaf89f450e7d57ff.png]: https://img-blog.csdnimg.cn/img_convert/d88f077f5f376a8aeaf89f450e7d57ff.png
[61f8df73255048aae76de8b24454c38e.png]: https://img-blog.csdnimg.cn/img_convert/61f8df73255048aae76de8b24454c38e.png
[dc779b8bcc78fd27af078d7b2f4d7819.png]: https://img-blog.csdnimg.cn/img_convert/dc779b8bcc78fd27af078d7b2f4d7819.png
[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[Download_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-Heapify.zip]: https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-Heapify.zip