【堆的认识及其优先级队列】java代码实现，保姆级教程学习堆和优先级队列(π—π堆积作用)

java8

帖子摘要：前言大家好我是良辰丫?我们又见面了前面我们讲了用链表实现的二叉树今天我们来接触堆的概念堆是一种特殊的二叉树只不过咱们的对底层原理是数组堆也是我们在做题中经常见到的那么接下来我们就慢慢的去接触堆认识堆......

/ C% k! `# N' _" B大家好，欢迎来到Java吧（www.java8.com），交流、学习Java技术、获取Java资源无任何套路，今天说一说：“【堆的认识及其优先级队列】java代码实现，保姆级教程学习堆和优先级队列”7 k0 B# J8 V: i/ T( W







& V6 t$ n8 R0 C. H# X 前言* L0 p& e9 L( E/ \$ Q3 C0 y
大家好我是良辰丫?我们又见面了前面我们讲了用链表实现的二叉树今天我们来接触
堆复制代码
的概念堆是一种特殊的二叉树只不过咱们的对底层原理是数组堆也是我们在做题中经常见到的那么接下来我们就慢慢的去接触堆( W% h) Q# z5 q# B/ x/ w1 `6 n
认识堆理解堆掌握堆。
& L; b0 L  J6 s( ]有疑惑可以和我一起讨论交流哦期待大家的来访。! a6 `8 A! n" p2 D( V

8 D; r* ?2 Z; L% j6 ^" _* Q& t

: u8 ?. K0 _: a/ \% I; | 个人主页良辰针不戳
4 \4 _; Q9 U! g: [ 所属专栏java数据结构
5 P8 n- F) L' N+ | 励志语句生活也许会让我们遍体鳞伤但最终这些伤口会成为我们一辈子的财富。
' j% F# _) X, o7 g0 X 期待大家三连关注点赞收藏。3 X6 J+ g* L' I% v7 W1 i
作者能力有限可能也会出错欢迎大家指正。
4 s0 V5 }. {1 j! b 愿与君为伴共探Java汪洋大海。1 `, U; g- b: w5 a7 k% F$ V
& v5 _! j# V; C" U

c9805839d7b34661904788e897718e10.gif (21.9 KB, 下载次数: 0, 售价: 1 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
c9805839d7b34661904788e897718e10.gif

1、堆

1.1 堆的概念

1.2 堆的基本性质

1.3 堆的创建

1.4 堆插入数据

1.5 堆删除数据

2、优先级队列

2.1 初识优先级队列

2.2 比较器Comparator实现优先队列大根堆

1、堆
1.1 堆的概念

! t$ o- k2 o6 }, @8 }8 w6 ], M
堆复制代码
在逻辑上是一种完全二叉树以顺序结构存储的方式存储的数据堆的模拟一般用数组其底层原理往往也是数组。堆分为大根堆和小根堆。$ k, {5 ]. S' q6 _! b

9 U+ R6 U, ^; Z; Z2 j

大根堆(最大堆):父亲节点比所有孩子节点都大。

小根堆(最小堆):父亲节点比所有孩子节点都小。 + R c4 w0 [7 Q0 c; I* b2 y

. O! L/ N/ B4 J) Q4 }
' I5 ?) F! M/ I- s( y如下图就是一个板板正正的大根堆+ y: S- R/ u' ?7 v' _
每个父亲节点都比所有孩子节点都大如果去掉下标为6的节点还可称为大根堆但是去掉了4号下标的节点就不是堆了因为堆的概念是完全二叉树那么为啥这么定义呢
- q& r7 s3 k& k9 K6 e因为在建堆的过程中需要一个个调整如果不是完全二叉树就不会调整成唯一的一个序列。
( d: k% {; s+ Z' f, j1 r " {* ^: {( Z- l6 z$ z" r

cd7910482bee4459ae89d4cfd6a7e802.png (90.58 KB, 下载次数: 0, 售价: 2 金钱)

堆的父亲节点总是大于或者小于所有孩子节点。

堆总是一棵完全二叉树。 - g5 G. R( N1 x3 u0 g

1.2 堆的基本性质
0 s8 F# _# M. W" l/ p/ |& B7 t
通过上面我们了解到
堆复制代码
是一种顺序存储的完全二叉树对于非完全二叉树不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节点就会导致空间利用率比较低。
0 E# C# | |2 l7 c" d. w
5 u4 ?+ M9 N5 F# O2 p
下图为一个小根堆图研究性质可以参考下图。

0f229bfcbdb646f6a04337324e4608da.png (91.62 KB, 下载次数: 0, 售价: 2 金钱)

如果i为0则i表示的节点为根节点否则i节点的双亲节点为 (i - 1)/2

如果2 * i + 1 小于节点个数则节点i的左孩子下标为2 * i + 1否则没有左孩子

如果2 * i + 2 小于节点个数则节点i的右孩子下标为2 * i + 2否则没有右孩子
. W6 d* h9 y9 C# ]
1.3 堆的创建

7 w3 \% k) q% G/ F0 ?9 ?) \) T 堆的创建顾名思义就是把一个个的数据插入到数组中然后调整即可一个个传数据太麻烦了我们直接传入一个数组。调整的时候我们采用向下调整。) t/ S! k; _) c% D
! i4 j# s4 M3 W9 I5 u) @* W

c4c128425b95426ebaa31701fe4b0e96.png (113.43 KB, 下载次数: 0, 售价: 1 金钱)

让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)

如果parent的左孩子存在即:child [/ol] 0 U8 h/ D0 k; ^

5a5df90fc7174d9d95c965bd4276a182.png (128.64 KB, 下载次数: 0, 售价: 3 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
5a5df90fc7174d9d95c965bd4276a182.png

9 ^% s, m3 m" k' ]( L" I5 C
下面以创建大根堆为例子。
2 s; K* u) A% p, a+ I o ' l9 a' [2 ?! ` S' s* z4 T

public void createHeap() {
//usedSize记录堆中元素个数
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
9 R) ^1 @; \: z. S
    }
: U! p+ T" v* k5 w7 h; p3 i4 R( r. l
   //向下调整
    private void shiftDown(int parent,int len) {
    //知道父亲节点然后扎到左孩子
        int child = 2*parent + 1;
        //要有左孩子
        while (child 
            //一定是有右孩子的情况下
# l, \; Y- k( z4 K1 ^
            if(child+1 
# g3 l& `, a9 Z8 j$ l* }& m3 Z' y
                child++;
  Y) v8 P- \3 U
            }
- N" P5 ^5 |6 |4 B$ [# X5 F
            //child下标 一定是左右孩子 最大值的下标
            if(elem[child] > elem[parent]) {
% @6 _% u) T: W. Y7 K0 N6 f4 n
                int tmp = elem[child];
% ~5 n/ Z% y2 u* A
                elem[child] = elem[parent];
                elem[parent] = tmp;
8 @( B' h) b" u( W& d
                parent = child;
                child = 2*parent+1;
                //左右孩子都比父亲小时跳出循环
& @6 s3 o3 W& p7 @
            }else {
: _4 e. q8 z" s4 }' Z
                break;
* N7 P: v% e- k6 m6 u$ t0 k
            }
) l  l. x$ ?! z4 D! S& t
        }
* H0 o' E1 C# ]1 w
    }
复制代码

, x2 S) N: ~1 V" ]8 T

4 R+ J, P# t% T( y( ?$ N/ U2 E9 d在调整以parent为根的二叉树时必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

调整情况下最坏的时候从根一路比较到叶子比较的次数为完全二叉树的高度。 8 j/ L. l3 G" H- Y J ]3 _; }! R1 I6 Q

/ d9 a& a3 ]5 [9 @% C C: J
那么问题又来了一颗普通的完全二叉树怎么调整成堆呢2 [. S4 f0 `' P8 U/ r
0 t: ]! @* C% A3 n; O
找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整1 h! @/ @/ E7 x' E

& F+ K- |8 G1 A$ V, M9 G# b

public static void createHeap(int[] array) {
+ _8 r  V8 a$ G% y) g/ i
int root = ((array.length-2)>>1);
% q* o. y, V) I& P# G! O
for (; root >= 0; root--) {
" h2 C0 Z  L+ H9 I( u' V/ [( P
shiftDown(array, root);
. @' m+ M& n' |* h; \
}
}
: r) H! C: R- E: x0 X
复制代码

- }' \/ x8 H/ d$ v' K1 d; W* {
注意
/ J8 l" X) k# W" W 建堆的时间复杂度为O(N)。5 K3 x3 a. \8 y L7 }) z$ J

$ v. L5 B; a4 ^0 D, P5 V
1.4 堆插入数据

8 m* R) K! w# X; O, Y( y, ]

先将待插入元素放到下标为usedSize的位置。(空间不够时需要扩容)

进行向上调整直到成为堆。
b7 |' c/ z4 O0 K |: `8 U

8 D0 ]: J1 e1 X
3 X8 x6 o/ U! g+ B) S有的伙伴可能会疑惑了刚刚学习了向下调整下载插入数据操作为什么又要向上调整呢
9 `0 `. `0 k9 N/ ~# r - s+ r. _, o# s; @

fc5e863ad96a49aea1610b92507c3fc6.png (142.61 KB, 下载次数: 0, 售价: 1 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
fc5e863ad96a49aea1610b92507c3fc6.png

private void shiftUp(int child) {
( u( `" g, Q! F% q+ v5 x
        int parent = (child-1)/2;
( r9 R$ g; ^' X
        while (child > 0) {
            if(elem[child] > elem[parent]) {
4 B; z8 O3 @' U7 M
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
3 C1 V% e- N5 H* `  m
                child = parent;
6 f  ?( }( l  ^# V: W0 m
                parent = (child-1)/2;
: d2 R4 v8 N4 O' t, J& O/ {3 p  }+ ?$ z( \
            }else {
, x; z5 F1 T  l& ~8 k! w, G! a
                break;
7 o3 b7 N0 f# g( j
            }
( c4 ?" x$ F! a; M( O1 C& ^
        }
    }
    //向上调整建堆的时间复杂度N*logN
' I9 H" W: \, h3 \+ G
    public void offer(int val) {
        if(isFull()) {
            //扩容
& b4 t2 d) I6 x: \8 J7 c
            elem = Arrays.copyOf(elem,2*elem.length);
" p' F9 U4 n7 S" t
        }
        elem[usedSize++] = val;
. X) ?  e3 b# k  a9 m$ D
        //向上调整
        shiftUp(usedSize-1);
    }
1 Q  V! E" Y9 ~0 E( Z1 O. U
复制代码

1.5 堆删除数据
3 t2 d$ v1 [/ p/ s( r7 Y

将堆顶元素对堆中最后一个元素交换

将堆中有效数据个数减少一个

对堆顶元素进行向下调整 7 t& B/ S/ V7 ^6 \; R/ F

892e3cbee2c34b5db1f1afd1a79abc92.png (127.68 KB, 下载次数: 0, 售价: 2 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
892e3cbee2c34b5db1f1afd1a79abc92.png

 public void pop() {
        if(isEmpty()) {
' i8 X2 g; O( ?+ F9 L3 l, a  i
            return;
        }
        swap(elem,0,usedSize-1);
2 K& \) \+ e$ b- v
        usedSize--;
/ F( C1 p% u/ \
        shiftDown(0,usedSize);
: B; M* X; `/ T1 ^
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
    private void swap(int[] array,int i,int j) {
, B+ x# L8 v! @, s) _
        int tmp = array[i];
5 H* Y8 F) T3 C: @3 x* x9 C* u" z4 {
        array[i] = array[j];
* Y( a$ n' a! p' `5 ^7 d
        array[j] = tmp;
    }
复制代码

2、优先级队列

( e. L+ h A7 E2 y& L _$ u6 U 说起对列大家肯定不陌生因为咱们前面的文章中学习过对列对列是一种先进先出的数据结构那么这里的
优先级队列复制代码
又是什么呢下面我们简单通过一个代码对优先级队列做一个认识。4 ]! S, E7 N% r- x4 i& i5 i" g

2 J4 v" x. A- C: @4 c/ v
2.1 初识优先级队列

public static void main(String[] args) {
        PriorityQueue[I] priorityQueue = new PriorityQueue();
7 R' L/ c. i6 k  o( c+ i* W
        priorityQueue.offer(3);
        priorityQueue.offer(4);
: D) ~4 L$ g' u# C) |* p
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        System.out.println(priorityQueue.poll());
# v% M2 v( ^/ ~+ f0 J' H0 L! F7 ]
        System.out.println(priorityQueue.poll());
: T7 M2 E1 ^& @/ q  V8 @7 r
        System.out.println(priorityQueue.poll());
/ t+ \) [& c7 `% W2 ~# n
        System.out.println(priorityQueue.poll());
; [! H6 W+ a- a: p( Q- G
    }
  T% _) R" K/ }. c- l/ B
复制代码

51d10544cc864b88a9bb47899bdf4f83.png (219.74 KB, 下载次数: 0, 售价: 1 金钱)

2023-2-2 02:12 上传

点击文件名下载附件
51d10544cc864b88a9bb47899bdf4f83.png

2 m4 F1 ~8 G- P, F
咿呀奇迹出现了通过上面的运行截图大家可以发现优先级队列并不遵守先进先出而是最小的数据先出来由此呢我们可以把它当成一种小根堆。( _3 R7 U0 z. |1 W" [  v% k' {

; a, L' P% U6 c# e* S4 f( x
看到这里大家又产生疑惑默认为小根堆那么如果我们想要使用优先队列作为大根堆呢

: j) }# b8 U+ g/ a6 M3 K* o: e/ G
办法当然是有的呀这里我们引入了比较器。那么究竟如何实现呢我们慢慢往下看。
' @# R8 W- I' {' J0 d! j, f0 U
3 ^4 ~) p$ H6 F0 d
2.2 比较器Comparator实现优先队列大根堆

; S1 s9 J3 e5 {  Z, T- x# x: g, [ 看到这里可能大家会感到疑惑什么是
比较器复制代码
呢
( W! J: k3 a2 L* \7 _5 ~" H java中的对象提供的方法只能比较对象是否相等而不能比较大小java提供了一些接口可以指定对象的属性进行比较比如根据学生信息的年龄进行排序。! t, z, }8 r! R$ ?( J# _- J9 a4 e
) y# P' ^- A$ z' l" ]% N
呜呜呜看了上面的解释还不明白没关系在我上一篇文章中详细介绍了比较器如果大家对比较器有疑惑请去具体学习比较器。: w; e) c4 V0 l6 p
对象的比较点击跳转文章# L0 \1 q/ K) D  K  K

& Y+ D  T# {& E* F& R( z

import java.util.Comparator;
& b* W5 Q' r9 O5 H' ]0 N( S3 N% `
import java.util.PriorityQueue;
class IntCmp implements Comparator[I] {
% P3 c* d* f+ v7 W1 V3 \  }
    @Override
0 H$ F2 O( m0 K; D" e
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
4 U" Y9 f3 g; a$ h) Y8 D! U
    }
}
public class Test02 {
    public static void main(String[] args) {
0 f6 d& ?* F1 i: |9 q6 N# ^( W
        PriorityQueue priorityQueue = new PriorityQueue(new IntCmp());
        priorityQueue.offer(3);
- i% [  o/ k4 c# u" j* }; z
        priorityQueue.offer(4);
# X' {; n) N% E- T" Y6 o: a0 [& o
        priorityQueue.offer(1);
# m2 e8 P( r/ v' Z+ \
        priorityQueue.offer(2);
9 j/ o; x& W) _2 F# P0 M
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
/ m% o6 j" B. d8 w2 Y
        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
' @$ W7 j* E* ^4 c4 c6 o) R; s4 N9 l! L
    }
}
8 b; _' e3 ^+ K4 {3 ^
复制代码

bad37a9af8ee4ff1afa252843b0202bb.png (424.74 KB, 下载次数: 0, 售价: 1 金钱)

【堆的认识及其优先级队列】java代码实现，保姆级教程学习堆和优先级队列(π—π堆积作用)

java8 LV9