@@ -402,33 +402,26 @@ public E peek() {
402
402
为了验证笔者小顶堆各个操作的正确性,笔者编写了下面这样一段测试代码,首先随机生成 1000w 个数据存到小顶堆中,然后进行出队并将元素存到新数组中,进行遍历如果前一个元素比后一个元素大,则说明我们的小顶堆实现的有问题。
403
403
404
404
``` java
405
- public class Main {
406
- public static void main (String [] args ) {
407
-
408
- int n = 1000_0000 ;
409
-
410
- MinHeap<Integer > heap = new MinHeap<> (n, (a, b) - > a - b);
411
-
412
-
413
- // 往堆中随机存放1000w个元素
414
- for (int i = 0 ; i < n; i++ ) {
415
- heap. add(RandomUtil . randomInt(0 , n));
416
- }
405
+ int n = 1000_0000 ;
417
406
418
- int [] arr = new int [n] ;
407
+ MinHeap< Integer > heap = new MinHeap<> (n, Comparator . comparingInt(a - > a)) ;
419
408
420
- // 进行出队操作,并将元素存到数组中
421
- for (int i = 0 ; i < n; i++ ) {
422
- arr[i] = heap. poll( );
423
- }
409
+ // 往堆中随机存放1000w个元素
410
+ for (int i = 0 ; i < n; i++ ) {
411
+ heap. add( ThreadLocalRandom . current() . nextInt( 0 , n) );
412
+ }
424
413
425
- // 循环遍历,如果前一个元素比后一个元素大,则说明我们的小顶堆有问题
426
- for (int i = 1 ; i < n; i++ ) {
427
- if (arr[i - 1 ] > arr[i])
428
- throw new RuntimeException (" err heap" );
429
- }
414
+ int [] arr = new int [n];
430
415
416
+ // 进行出队操作,并将元素存到数组中
417
+ for (int i = 0 ; i < n; i++ ) {
418
+ arr[i] = heap. poll();
419
+ }
431
420
421
+ // 循环遍历,如果前一个元素比后一个元素大,则说明我们的小顶堆有问题
422
+ for (int i = 1 ; i < n; i++ ) {
423
+ if (arr[i - 1 ] > arr[i]) {
424
+ throw new RuntimeException (" err heap" );
432
425
}
433
426
}
434
427
```
@@ -523,29 +516,26 @@ public class PriorityQueue<E extends Comparable> implements Queue<E> {
523
516
我们的测试代码很简单,因为我们优先队列底层采用的是小顶堆,所以我们随机在优先队列中存放 1000w 条数据,然后使用 poll 取出并存到数组中,因为优先队列底层实现用的是小顶堆,所以假如我们的数组前一个元素大于后一个元素,我们即可说明这个优先队列优先级排列有问题,反之则说明我们的优先队列是实现是正确的。
524
517
525
518
``` java
526
- public static void main(String [] args) {
527
- // 往队列中随机添加1000_0000条数据
528
- PriorityQueue<Integer > priorityQueue = new PriorityQueue<> ();
529
- int n = 1000_0000 ;
530
- for (int i = 0 ; i < n; i++ ) {
531
- priorityQueue. offer(RandomUtil . randomInt(1 , n));
532
- }
533
-
534
- // 将优先队列中的数据按照优先级取出并存到数组中
535
- int [] arr = new int [n];
519
+ // 往队列中随机添加1000_0000条数据
520
+ PriorityQueue<Integer > priorityQueue = new PriorityQueue<> ();
521
+ int n = 1000_0000 ;
522
+ for (int i = 0 ; i < n; i++ ) {
523
+ priorityQueue. offer(ThreadLocalRandom . current(). nextInt(1 , n));
524
+ }
536
525
537
- for (int i = 0 ; i < n; i++ ) {
538
- arr[i] = priorityQueue. poll();
539
- }
526
+ // 将优先队列中的数据按照优先级取出并存到数组中
527
+ int [] arr = new int [n];
540
528
541
- // 如果前一个元素大于后一个元素,则说明优先队列优先级排列有问题
542
- for (int i = 1 ; i < arr. length; i++ ) {
543
- if (arr[i - 1 ] > arr[i]) {
544
- throw new RuntimeException (" error PriorityQueue" );
545
- }
546
- }
529
+ for (int i = 0 ; i < n; i++ ) {
530
+ arr[i] = priorityQueue. poll();
531
+ }
547
532
533
+ // 如果前一个元素大于后一个元素,则说明优先队列优先级排列有问题
534
+ for (int i = 1 ; i < arr. length; i++ ) {
535
+ if (arr[i - 1 ] > arr[i]) {
536
+ throw new RuntimeException (" error PriorityQueue" );
548
537
}
538
+ }
549
539
```
550
540
551
541
## JDK 自带 PriorityQueue 使用示例
0 commit comments