数学建模社区-数学中国
标题:
十大经典排序算法之堆排序(Java语言)
[打印本页]
作者:
杨利霞
时间:
2020-4-23 15:00
标题:
十大经典排序算法之堆排序(Java语言)
2 ?4 V3 A. Q2 f' u& h* G3 A2 J! ]$ u
十大经典排序算法之堆排序(Java语言)
- n, r7 e; h4 P; q# _& X6 s
文章目录
( _# m7 w) u" O ?
6 F7 }* \4 w0 p9 R
什么是堆
7 X* c/ N4 f+ ~! L: x
如何进行堆排序呢
8 q8 t2 [( a2 `. Z, g
用数组构建一个堆
% u% ]$ h- {4 [0 t- f2 v& v$ u
上代码
, O: n1 y7 V# }( o" z0 o! e
什么是堆
, N9 A: R, ]- F# i$ z' Q0 S
, J- N) H" s( z4 l& M$ G
在了解什么是堆之前一定要先了解什么是完全二叉树
. r6 A! C# d6 w0 J0 Q+ P# V3 w( |, G
看一下百度百科的介绍
# G! }6 r8 e! i% l- n
2 b ^- I+ ?0 {
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
4 m: s1 N, o# U
百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下
% L* ~! M0 \( |; d" G0 |
: N5 I9 g+ O- L5 J' {
完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
- U3 \) \! L0 m J* V& B3 |% {
(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
) B6 J; `; X0 I8 a4 {& ]; \& b, o
(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。
$ ~# S! Q% T* ]3 Y! x! G" T1 [) p
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
3 h' s7 f$ ~+ l( x1 q- R. G1 d
那么在了解到什么是完全二叉树之后,我们再来看什么是堆
; ~4 t; l0 w- p! s! i9 F" H1 e
堆有以下两个性质
- X1 O6 G) W+ O( N+ q$ n5 Z- `% P A
. ?7 I1 D. Y. f
1 堆中某个节点的值总是不大于或不小于其父节点的值;
4 l2 N$ @: \" g" @2 ?& p9 h
2 堆总是一棵完全二叉树。
. I' a( h" b0 W
其中堆顶就对应二叉树的根
@" n5 A. v' F. r5 P; p1 v
! b" | h/ C) A4 t
堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分
3 V+ C) w' o9 p7 j/ O" i& W
) m+ b$ R) p" Y1 @
当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆
E, E" O0 K: R t9 _* U
如何进行堆排序呢
; F4 P8 {. F" Z+ G
5 j2 U2 T1 w' k9 ?/ `0 U
堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的
* n5 L& V& V1 n
) ^+ a0 j( E) @/ Q( X
用数组构建一个堆
0 W* f# p1 X7 R! Q2 j+ |
- U* ~1 [- g& p% q
因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
2 o: E/ k) ]( Q' K& S' u
对于用数组存储的二叉树,我们可以用如下方法来定义:
# R% C5 Z# X; K, g* X8 v7 F
假设当前节点的下标为 n
. c% m* S" r. U+ e+ q: y. {
- M2 d$ i% P! R/ T
1、那么他的左子节点的下标 2*n + 1
: _5 h0 S; H$ U# b/ k+ E- O
2、那么他的右子节点的下标 2*n + 2
# s# h& V9 m1 O8 ^/ K6 j
3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1
6 [, p3 S, y( F' e6 G7 k
4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
' ~/ v1 O! l" R6 l# |
那么有了上面四条性质,我们就可以开始动手了
; a' G0 }+ j- ]4 W- I
1 L) r4 f E0 U% c0 L) f5 j
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层
9 t' z3 I1 N3 Z( ?
2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
' x% S, \1 V, V: F6 ~0 h& ^6 W
3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
5 v) _7 X# B4 ~: v' v
6 u2 E% J- B2 r8 Y3 T
堆排序的性质
/ w! L/ p8 w; k* V
1 p0 u9 |2 i. x# W8 z) g9 `1 S
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
5 p5 H2 z7 m+ \
堆排序 Heap n*logn n*logn n*logn 1 不稳定
# k/ B) l* d, ~ e$ c8 x" S
上代码
! L. M: y3 U/ o9 |) ~6 l: C
n: G0 ]$ w4 V/ L2 h* y8 f
/**
2 k' s, p: E5 L7 A% T' i+ j" x
* 交换第n和m个元素
% w( Y- L: D6 I+ u# u% U' W. j
*/
/ u& z, ^' Z2 @6 V- {4 S+ L& T O
private static void swap(int arr[], int n, int m){
/ ^% Q% q* [, L- W( t: Y3 x9 w: m, v
int temp = arr[n];
) t5 s/ s7 `, r2 Z1 E- C+ v. l
arr[n] = arr[m];
& G* H4 _! y X8 L
arr[m] = temp;
7 r5 q" T& i4 V/ J) F) J
}
( m; s7 [7 y. E# l" O( o
. k% Q! n7 [- q# \6 L
/**
" a6 @( f9 E6 X4 f8 N M
* 调整指定节点和其子节点
" U2 [0 i4 `& C8 ?' k. G
*
@param
tree 整棵树
/ b/ @' x, C+ I' l
* @param n 数组长度,树的元素个数
/ B/ X* }8 D+ R, {% b" K* ^
* @param i 要调整的节点的下标
& {# v- l, N4 A* {/ x0 ?+ r
*/
* |2 u, y& V2 ^* ]; X- @* G
private static void heapIfy(int tree[], int n, int i){
+ h" ^; i4 L! W- @& W! z+ k9 d. M( V
if(i >= n){
! P9 u+ ^" @ D3 t5 i' z
return;
$ i& y0 @! e/ n( z) G
}
1 D! w, z, d3 X
int c1 = 2 * i + 1;//左子节点的下标
$ R8 i6 A0 |) `- l# u) ?
int c2 = 2 * i + 2;//右子节点的下标
( _, q. |) _- m) s \1 x# _
int max = i;//假设父节点是最大的
3 O) C: h: ^* t& L
//找出最大值的下下标
8 Y3 r- g5 g: C5 i, m9 `4 `. i
if(c1 < n && tree[c1] > tree[max]){
0 ~7 {' }1 t( H, e; q' c
max = c1;
4 v: ?! |( f Z8 N
}
$ |) K( ]" Q; v- k
if(c2 < n && tree[c2] > tree[max]){
6 R/ V+ }( f' M7 D! V! h& {
max = c2;
4 ^ \+ o/ X# b* D: {8 m0 x4 L
}
1 Z: U r) W" A1 V& b$ l0 t
if(max != i){//如果最大值不是父节点,需要做换位置操作
4 S$ V% T3 Q3 U. @$ c6 B
swap(tree, max, i);
8 @. G( W# K: I: a
//此时,i节点被换成最大值了,符合大顶堆的性质
/ @* H7 k* |# d5 e7 S6 l* c
//但是换到下面的节点不能保证比他的两个子节点都要大
& i+ F$ f; f" B) T& X
//所以被换位置的节点继续调整
" [: ~% d3 u+ b
heapIfy(tree, n, max);
2 x1 w; i. E9 T( c
}
5 G0 t: H. {6 ^# O3 S5 h
}
) J& \3 {- Y8 a2 d d9 A" s
% H6 [5 ^( { \
/**
/ }4 x, _2 S9 T( D2 K0 o3 a7 j6 E4 m7 I/ [
* 完整构建大顶堆
$ i4 i8 T J+ {0 p6 H
* @param arr 用于构建堆的数组
; {& u' E+ z6 ~9 l- o* @2 T
* @param n 堆的最后一个节点的下标
: N( o0 i! ?/ I, x
*/
0 v3 g7 Q4 m/ l; o2 `& j1 [
private static void buildHeap(int arr[],int n){
8 K( p% _- |) n7 Z5 H+ A$ r! n+ ~
int lastNode = n - 1;
4 R3 N0 s: H S& X2 T( @( g {
int parent = (lastNode - 1) / 2;
7 ~2 f! u& u1 ?; g( @
for (int i = parent; i >= 0; i--){
3 w2 e5 @0 P1 t' n/ ~$ D
heapIfy(arr, n, i);
8 E6 k4 G% ^7 H- p7 o' _
}
h. u! o+ g& c0 U1 k
}
, K: U$ u( n/ H8 f: `" O
8 ^! ]8 t" c: N/ {2 x; s
/**
. r$ R% I& Z( w2 ^ i, }& b# @
* 堆排序
5 g8 F) i# A0 j4 O4 o4 y$ M! ^0 ?
* @param arr 待排数组
! s8 N2 ?1 m/ e; K! n
*/
2 t9 ], t# a. I% W/ m9 W
public static void sort(int arr[]){
7 Y& v5 M# _# |% ]
buildHeap(arr, arr.length);//先构造大顶堆
$ B* z W) k* m
//每次构建堆后将根节点和最后一个节点进行交换
9 w# x' ]& a# ` `
//然后砍断最后一个节点
/ X9 Y" V* l, L
//所以从最后一个节点向前循环
! x- q l& M0 ~: S/ L
for (int i = arr.length - 1; i > 0; i--){
' l8 f6 d$ |: n: b3 Z
swap(arr, 0, i);
! J- b$ K4 l1 C9 P* U' W
heapIfy(arr, i, 0);
3 _0 ]( P+ e9 }+ [
}
! w0 X) n; t' c
}
- D( U, u. A% l, v( d
————————————————
; W% e/ u( @; R; V: _% r
版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
" ~* K/ V2 V! H3 F( g5 [" ^) }
原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644
+ U6 i5 K% Z* w( j9 S( V
! A [7 z' T& U ~2 o& Q
9 \7 z; C/ `9 J6 H/ r" b
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5