十大经典排序算法之堆排序（Java语言）

杨利霞

9 _+ H- B3 |' ~十大经典排序算法之堆排序（Java语言）
+ m1 S  Q" \* b文章目录
% l! Y( f: j/ m8 h! c: L
: P2 A6 X) n: i4 G# x/ R: V! d什么是堆
2 ~" ~" v/ P  ]. h. }( w- ]如何进行堆排序呢
( u" w+ t6 `- z, y4 ~2 c/ ~: R用数组构建一个堆
上代码
: c3 C, k( ~  a; V" l什么是堆

在了解什么是堆之前一定要先了解什么是完全二叉树
. d" D. U) w3 ~, y4 i% e看一下百度百科的介绍

1 W6 F0 K' r! n' P$ y) `若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
百度百科拗口版性质介绍，能看懂上面的就行，下面的大概看下

4 V* o# T0 p: b  Z; q9 h! |3 g+ o完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）
: D9 c7 L& M, N(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。
1 `3 Z3 x* B8 }% ]/ d9 h一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
那么在了解到什么是完全二叉树之后，我们再来看什么是堆
# x8 R" R2 N: I- D! Q堆有以下两个性质

: E+ N, o0 s: U: Q1 堆中某个节点的值总是不大于或不小于其父节点的值；
2 堆总是一棵完全二叉树。
其中堆顶就对应二叉树的根
2 k0 [' |/ d1 J1 D$ u4 w
堆又分为大顶堆和小顶堆，根据堆的第一个性质来进行区分
' C4 W- b/ J: F2 e4 V: \5 v
当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆，反之为小顶堆
如何进行堆排序呢
" W* F# p+ ^6 _, r: `- {
堆排序，其实就是每次构造出一个大顶堆或者小顶堆，然后取出堆顶的值，再将剩下的值重新构造成大顶堆或者小顶堆，最终到堆里的值全部取出来，取出来的数就是排好序的

用数组构建一个堆
) d* K, O2 m1 k4 T8 Y- ^9 @/ L0 I* ?
因为堆是一颗完全二叉树，所以我们可以用数组来对其进行存储
( v; n3 c5 F; t对于用数组存储的二叉树，我们可以用如下方法来定义：
假设当前节点的下标为 n

1、那么他的左子节点的下标 2*n + 1
2、那么他的右子节点的下标 2*n + 2
3、他左边的节点是 n-1，如果当前节点是第 h 层的最左节点，那么第h-1层的最右节点的下标就是 n-1
4、根据1、2可以推出来n节点的父节点是 (n-1)/2，不管当前节点是父节点的左子节点还是右子节点，都用 (n-1)/2就行了，因为整型数字相除小数点后面的会被截断
+ t. {5 a. d7 c9 s5 w# q( _8 }9 ^- k那么有了上面四条性质，我们就可以开始动手了
' H" F- n( N' {  Y0 F
$ C; f% t, q0 r8 C* T5 [9 p+ P' U1、假设我们要构建的堆是大顶堆，那么根据大顶堆的性质，任意节点都比它的左右子节点要大，所以我们肯定有个heapify方法，该方法调整指定节点和其子节点的位置，并且继续调整被调整的子节点和孙子节点的关系，直到没有调整或者到数的最底层
2、然后我们要有构造大顶堆的方法，构造大顶堆就是从最后一个节点的父节点开始调整，接设最后一个节点的父节点是n，那么我们就将n，n-1，n-2 ··· ··· 0，这些节点逐次，从大到小调用heapify方法，这些节点都调整完成后，大顶堆就构造完成了
3、接下来就开始将堆顶和堆尾互换，并砍断堆尾的操作了，由于互换之前，这是一个符合条件的大顶堆，但是换完只有只有一个堆顶这里不满足了，那么我们重新调整一下堆顶的三个元素就可以，还是调用heapify方法，这个方法会自上而下的重新调整堆，使其成为一个大顶堆

- e( i1 {1 i2 m" t& S, d堆排序的性质
) l! _1 X! L2 _+ b
  `* X# e* t1 N* l3 {. ?中文名称        英文名称        平均时间复杂度        最坏时间复杂度        最好时间复杂度        空间复杂度        稳定性
9 ~& p: {% J, R* m# L0 A堆排序        Heap        n*logn        n*logn        n*logn        1        不稳定
; H$ i' s7 F% v: d上代码
9 w- U6 O+ P" [7 l+ }
6 p+ I8 ?$ c- n9 j( B4 C8 L/**
- H4 d7 P0 P" H+ {- [) r * 交换第n和m个元素
, M& W8 ]4 T) p& R+ p */
4 _0 d+ J+ i8 ^0 W1 n) \1 Bprivate static void swap(int arr[], int n, int m){
! r9 ?7 U. X% m9 u# B; @    int temp = arr[n];
4 E! ?+ e1 {2 `/ E7 d/ q4 R    arr[n] = arr[m];
( b" b" I6 h8 C  N# z$ V: y    arr[m] = temp;
% x- `, `+ ~, P8 |}

/**
* 调整指定节点和其子节点
$ Q4 }, }3 p& D' c( h7 p& h * @param tree 整棵树
6 @% Y# ~  p, [, ?6 F * @param n 数组长度，树的元素个数
* @param i 要调整的节点的下标
9 S% Z  {7 s6 ]- a+ g/ c9 J6 v */
private static void heapIfy(int tree[], int n, int i){
+ F) e8 }) p* I: _    if(i >= n){
; n: B% d2 y3 U        return;
; I) w& X; L0 `5 ^    }
    int c1 = 2 * i + 1;//左子节点的下标
( R4 U- r  G6 ]9 o    int c2 = 2 * i + 2;//右子节点的下标
    int max = i;//假设父节点是最大的
: Z/ U2 z. w+ ^- L9 Y+ ?* _    //找出最大值的下下标
  x6 `8 X9 I6 e9 }% A. F' a6 D    if(c1 < n && tree[c1] > tree[max]){
9 }1 i* ^3 r+ H7 C) p! _8 ^        max = c1;
* W0 d* _" b; E+ ~6 o. l    }
& K4 A5 }! u3 Q% {( ~7 L/ m    if(c2 < n && tree[c2] > tree[max]){
( O# W2 s; Y5 V+ ]        max = c2;
    }
    if(max != i){//如果最大值不是父节点，需要做换位置操作
        swap(tree, max, i);
& O7 W) I, Q5 v2 s& S/ B# {! N        //此时，i节点被换成最大值了，符合大顶堆的性质
        //但是换到下面的节点不能保证比他的两个子节点都要大
7 {* W( ~2 l. v4 g) J        //所以被换位置的节点继续调整
        heapIfy(tree, n, max);
2 h! ^2 ^* A1 a9 H$ z    }
}
1 L0 X# d- f, ^  N
0 m7 G0 Z0 y* h1 W! H0 q; g/ d/**
- ~, w/ K2 D/ t2 C$ P * 完整构建大顶堆
* @param arr 用于构建堆的数组
# X0 a" l% F: b- |, q" } * @param n 堆的最后一个节点的下标
*/
1 e5 v# i7 y/ q4 g, o8 H2 F  z* r6 y2 yprivate static void buildHeap(int arr[],int n){
    int lastNode = n - 1;
% S& j+ Q# [# }% j    int parent = (lastNode - 1) / 2;
1 y; I8 Q& B* q1 O    for (int i = parent; i >= 0; i--){
- D" ~9 A% ]1 Z9 H) |$ a0 _        heapIfy(arr, n, i);
/ m0 \" E" W, K$ O) l0 f    }
}

/**
' t9 m  {" X( p& m * 堆排序
* @param arr 待排数组
*/
, n, f; t- x4 k8 d8 V: ^public static void sort(int arr[]){
    buildHeap(arr, arr.length);//先构造大顶堆
    //每次构建堆后将根节点和最后一个节点进行交换
4 s3 [# W) _5 h9 p( b; V    //然后砍断最后一个节点
    //所以从最后一个节点向前循环
    for (int i = arr.length - 1; i > 0; i--){
0 y9 Q/ b+ c, q* I2 d! ?% t9 f        swap(arr, 0, i);
9 q6 j& ]$ B. ^) ]2 |( O" r% k& p0 \- e        heapIfy(arr, i, 0);
    }
}
————————————————
版权声明：本文为CSDN博主「qq_34912889」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
! g' n% P$ X& G5 R) o. H8 ]原文链接：https://blog.csdn.net/qq_34912889/article/details/105690644
" E5 W- U) f: e2 L2 w
  D' t2 u+ G8 c8 h7 A8 _