基础堆排序 |
最编程
2024-04-19 08:20:39
...
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];
}
}
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];
}
}
推荐阅读
-
IM 开发人员零基础通信技术入门 (I):百年通信交换技术(上)
-
2.5 Java 全栈开发前端 + 后端(全栈工程师进阶路径) - 前端框架 VUE3 - 基础 - Vue 路由 - 程序化路由
-
Java 基础-day11-接口;多态性案例练习
-
15C++ 结构基础知识点(二)
-
JAVA 基础 (38) 理解 JAVA 的四大特性(封装、继承、多态、抽象)
-
第 12 章 软件测试基础(第一部分)概念、质量保证、测试用例、测试执行过程-III。
-
Python 定量金融基础 | Python
-
Java 零基础物联网入门 (2):Power 104 章程详情
-
Raspberry Pi 4 裸机基础教程:环境设置
-
etcd 实用基础 (II)