现在的位置: 首页 > 面试题 > 正文

基础堆排序

2022年01月10日 面试题 ⁄ 共 2126字 ⁄ 字号 暂无评论
博客主机

一、概念及其介绍

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

 

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

 

二、适用说明

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

 

三、过程图示

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

 

 

 

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

 

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

 

 

 

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

 

 

 

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

 

 

 

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

 

 

 

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

 

 

 

四、Java 实例代码

源码包下载:Download

 

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];

}

}

Wopus问答

【上篇】
【下篇】

Wopus问答

给我留言

留言无头像?


×