数学建模社区-数学中国
标题:
十大经典排序算法之堆排序(Java语言)
[打印本页]
作者:
杨利霞
时间:
2020-4-23 15:00
标题:
十大经典排序算法之堆排序(Java语言)
& t; m: I6 V4 ?+ q; {
十大经典排序算法之堆排序(Java语言)
1 g! o. k$ S3 X1 R" a' |0 d& h
文章目录
* o, k0 B" p' Q" {0 v9 N6 i
7 q8 ~2 h% O6 x) m2 T0 D a
什么是堆
( S$ c) S8 y9 q# t
如何进行堆排序呢
9 p$ E' V* |$ Y4 t+ [: v
用数组构建一个堆
6 x% U* F: P% A3 a
上代码
o @5 _8 S Y2 G6 y
什么是堆
" _6 p8 K8 l, x$ E* b" J# [
* {, X, z' R( \. h' } }
在了解什么是堆之前一定要先了解什么是完全二叉树
/ v* ^& B2 `3 V' D2 C% V6 G% N1 w
看一下百度百科的介绍
' D- |- {' H! g* P$ N
. k+ I" `' [* K: j
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
; s1 I& N- ?# ]/ D- d( w. ~
百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下
6 p, z: K, p' W0 G
p+ R1 ~2 o/ z8 |1 q
完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
. m& z! U0 Q# F/ ?1 K+ h2 ]
(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
( V, x" E0 Y0 \% p3 ^
(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。
2 V$ Z7 H* H% H' ~. ^* G. ]
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
z7 r' e. x$ I8 y
那么在了解到什么是完全二叉树之后,我们再来看什么是堆
& Q* @' [$ a( z' J' s# p3 ]% W
堆有以下两个性质
" W5 ]# K' W6 u5 B
1 j; c$ J; ?$ A q0 y
1 堆中某个节点的值总是不大于或不小于其父节点的值;
3 ], U1 y: U8 v7 g. k# C
2 堆总是一棵完全二叉树。
! @4 A4 M/ a! g- N1 X/ o
其中堆顶就对应二叉树的根
5 ]- Q) M! L: y9 {7 \5 E0 { L
+ o4 I( T4 {# J
堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分
; s# B: E' a* J
6 x6 Q1 z. t/ i* v- j
当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆
2 f+ m2 s! r- g
如何进行堆排序呢
1 | P8 I$ e( Y
) d6 U; b- _# a; F( p8 J; M# ~, A
堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的
% G( W" ^2 H1 r) l5 [7 O
' C0 C3 c8 q: I: {5 I5 b8 V
用数组构建一个堆
' E- I: e) T0 R- ?; ~' k
. D6 b& i# B; _* l8 {! I
因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储
9 C/ L S. U' _
对于用数组存储的二叉树,我们可以用如下方法来定义:
+ I }3 F8 a; N3 g. p' n
假设当前节点的下标为 n
- s% G+ F# c- [9 b9 q
: N: B# A% R: U1 c) Z# {) T
1、那么他的左子节点的下标 2*n + 1
, A) v4 C+ k6 O+ u8 r
2、那么他的右子节点的下标 2*n + 2
& S0 m) k- z4 `
3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1
; S. h$ y% J- ?3 S7 `- R3 }
4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
+ S3 B1 v% g) f+ {
那么有了上面四条性质,我们就可以开始动手了
7 r$ A2 ^- J# \7 ]& {2 _
1 e: x) C7 y3 K& K3 f
1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层
$ o" j! t' K K) g6 l+ H
2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了
6 x( y$ k+ J7 A, ]; {6 ~; Z
3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆
# Y* O! S( ]: Q; v8 ~
5 V* |* N T" d. p2 o
堆排序的性质
. K6 \( I" D3 B! S0 u* S8 _
8 N+ W$ C& O" f0 q$ H+ l/ E
中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
, M: y, h( g7 e! q* c
堆排序 Heap n*logn n*logn n*logn 1 不稳定
3 p5 u4 q5 w9 k" u h- {
上代码
5 s8 N( U8 d ]! a
( u1 s n# F' Z) ~
/**
" x/ h9 ?2 E9 R6 \+ h* _' I( B
* 交换第n和m个元素
) B# q: R3 l2 Y0 q7 }, ?& f
*/
( y O* v' G* h5 r- t" J
private static void swap(int arr[], int n, int m){
4 \6 H* `! D! A& }
int temp = arr[n];
. N4 V* t4 W0 d$ k. V
arr[n] = arr[m];
' ^9 N: e& i' W- ~2 z+ n
arr[m] = temp;
6 x+ `# T) g. t
}
$ L* F* {: [$ S5 n& F" t1 r1 F4 K+ m
9 N$ T/ N4 o: Q' C
/**
6 c- E' t% _5 o) l/ ^0 X# s/ k; h
* 调整指定节点和其子节点
8 K7 J& g* u' y
*
@param
tree 整棵树
4 `$ C: P* W v ] Z
* @param n 数组长度,树的元素个数
2 i' J( z6 j+ G0 k8 x. T0 ], X
* @param i 要调整的节点的下标
/ M W) D" _4 {9 c2 I( l) z7 x0 C+ ~
*/
$ Q! p+ F6 u. G" [- P
private static void heapIfy(int tree[], int n, int i){
5 d5 Y1 X( R# k# x t
if(i >= n){
8 n4 x3 F3 i# G/ d9 v
return;
6 O! [1 o: p- U7 }/ L+ @0 c
}
3 _" V/ G+ C$ q
int c1 = 2 * i + 1;//左子节点的下标
" m$ P5 y( o7 d3 m* n7 \/ f" _
int c2 = 2 * i + 2;//右子节点的下标
2 w+ T, D$ s5 S! {, g% s$ E( `$ q
int max = i;//假设父节点是最大的
3 Z. o; u3 d: O# Q0 o
//找出最大值的下下标
3 o6 U# }4 f% J; c; H& j
if(c1 < n && tree[c1] > tree[max]){
+ m4 n8 L( O8 X
max = c1;
6 i! |. @% @, p+ L, ] o% C9 p5 l
}
7 a3 @4 t& a' f' }' S; R
if(c2 < n && tree[c2] > tree[max]){
5 Z' l' ?5 Z" ~
max = c2;
; k: Q8 X2 e& h0 C1 W: m
}
F I; ?& F) J& F: u
if(max != i){//如果最大值不是父节点,需要做换位置操作
& ^% f' N" E/ q6 {; t6 k; X
swap(tree, max, i);
a+ I9 o. I. y7 S. R+ c. }
//此时,i节点被换成最大值了,符合大顶堆的性质
# E" D; V8 ~) s. ^
//但是换到下面的节点不能保证比他的两个子节点都要大
2 @) t! k3 e% `; \5 k4 t/ x6 i
//所以被换位置的节点继续调整
! p1 r) ?3 I$ J; B1 K; B1 j& u! s
heapIfy(tree, n, max);
0 x% _% w+ p- g8 @
}
# i8 r5 q* c5 h& a0 A3 e; S, I' l# _" y
}
/ t. l! [8 Z s' c1 ]
2 |9 z8 Z. p- [% V# i
/**
# R2 B- w9 x7 w: ~
* 完整构建大顶堆
3 V r( Y' ~$ F3 u b
* @param arr 用于构建堆的数组
/ y8 ? }2 b- q1 q
* @param n 堆的最后一个节点的下标
. I$ A2 K% Q7 y. x- q/ |# R
*/
4 ?- n! b2 W2 d' P- a
private static void buildHeap(int arr[],int n){
9 _) G, t, I( U) b b
int lastNode = n - 1;
0 D4 v. f3 T% e
int parent = (lastNode - 1) / 2;
5 h* ?6 ?. F& @. X, s
for (int i = parent; i >= 0; i--){
& p9 Y! t" ]3 R6 v6 J5 `2 C1 b0 Y
heapIfy(arr, n, i);
' t! |1 T+ P0 }# z" h$ |
}
2 t, Z* ~2 f' O, K# m* t
}
: d) u+ o" j2 Q' S+ u
# [8 g) b. v/ m4 t
/**
6 D! O4 P% }! ~& E
* 堆排序
1 f8 o; d# c, }) M: h0 B
* @param arr 待排数组
2 z d9 J/ n( K: p/ {! M) C+ a, Q+ u
*/
& F- l, H' f; A$ C6 @/ Y7 h
public static void sort(int arr[]){
# u9 X- \- L& [) n+ J$ H$ E8 s8 |$ l y
buildHeap(arr, arr.length);//先构造大顶堆
. w( z0 ^, ]+ k' ^8 I2 O0 ?
//每次构建堆后将根节点和最后一个节点进行交换
: K* d8 y& k! Z8 M+ a
//然后砍断最后一个节点
4 e. s+ W) f: z' ~# s1 x$ j9 e+ c! f
//所以从最后一个节点向前循环
& Z# u$ _0 H1 J& B" t
for (int i = arr.length - 1; i > 0; i--){
4 a% B3 E7 ]7 B) Z; E0 V
swap(arr, 0, i);
; C+ X( v1 H4 L/ J
heapIfy(arr, i, 0);
: ^8 q: L2 B$ S; y5 Q1 y
}
3 } w9 b3 V! F& p Y
}
$ N# O4 r% d5 v+ Q, K1 O
————————————————
/ X% U6 S! G# f# H D
版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
. {, |+ u7 e$ s
原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644
4 }& p5 T! P9 |/ K
- F( m- g( R+ T! L5 v3 C+ X8 j; `
) [1 N6 S. n' p2 u0 i' S: A
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5