8000 [docs update]优化二叉堆和 PriorityQueue的测试代码 · lab408/JavaGuide@1a81d8f · GitHub
[go: up one dir, main page]

Skip to content

Commit 1a81d8f

Browse files
committed
[docs update]优化二叉堆和 PriorityQueue的测试代码
1 parent ad01bdc commit 1a81d8f

File tree

1 file changed

+31
-41
lines changed

1 file changed

+31
-41
lines changed

docs/java/collection/priorityqueue-source-code.md

Lines changed: 31 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -402,33 +402,26 @@ public E peek() {
402402
为了验证笔者小顶堆各个操作的正确性,笔者编写了下面这样一段测试代码,首先随机生成 1000w 个数据存到小顶堆中,然后进行出队并将元素存到新数组中,进行遍历如果前一个元素比后一个元素大,则说明我们的小顶堆实现的有问题。
403403

404404
```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;
417406

418-
int[] arr = new int[n];
407+
MinHeap<Integer> heap = new MinHeap<>(n, Comparator.comparingInt(a -> a));
419408

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+
}
424413

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];
430415

416+
//进行出队操作,并将元素存到数组中
417+
for (int i = 0; i < n; i++) {
418+
arr[i] = heap.poll();
419+
}
431420

421+
//循环遍历,如果前一个元素比后一个元素大,则说明我们的小顶堆有问题
422+
for (int i = 1; i < n; i++) {
423+
if (arr[i - 1] > arr[i]) {
424+
throw new RuntimeException("err heap");
432425
}
433426
}
434427
```
@@ -523,29 +516,26 @@ public class PriorityQueue<E extends Comparable> implements Queue<E> {
523516
我们的测试代码很简单,因为我们优先队列底层采用的是小顶堆,所以我们随机在优先队列中存放 1000w 条数据,然后使用 poll 取出并存到数组中,因为优先队列底层实现用的是小顶堆,所以假如我们的数组前一个元素大于后一个元素,我们即可说明这个优先队列优先级排列有问题,反之则说明我们的优先队列是实现是正确的。
524517

525518
```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+
}
536525

537-
for (int i = 0; i < n; i++) {
538-
arr[i] = priorityQueue.poll();
539-
}
526+
//将优先队列中的数据按照优先级取出并存到数组中
527+
int[] arr = new int[n];
540528

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+
}
547532

533+
//如果前一个元素大于后一个元素,则说明优先队列优先级排列有问题
534+
for (int i = 1; i < arr.length; i++) {
535+
if (arr[i - 1] > arr[i]) {
536+
throw new RuntimeException("error PriorityQueue");
548537
}
538+
}
549539
```
550540

551541
## JDK 自带 PriorityQueue 使用示例

0 commit comments

Comments
 (0)
0