JDK8中关于最小堆的实现（PriorityBlockingQueue）

本文主要是介绍JDK8中关于最小堆的实现（PriorityBlockingQueue），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java.util.concurrent.PriorityBlockingQueue#siftUpComparable
代码很简单，记录一下。

    /*** Inserts item x at position k, maintaining heap invariant by* promoting x up the tree until it is greater than or equal to* its parent, or is the root.** To simplify and speed up coercions and comparisons. the* Comparable and Comparator versions are separated into different* methods that are otherwise identical. (Similarly for siftDown.)* These methods are static, with heap state as arguments, to* simplify use in light of possible comparator exceptions.** @param k the position to fill* @param x the item to insert* @param array the heap array*/private static <T> void siftUpComparable(int k, T x, Object[] array) {Comparable<? super T> key = (Comparable<? super T>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = array[parent];if (key.compareTo((T) e) >= 0)break;array[k] = e;k = parent;}array[k] = key;}

添加测试类：

import java.util.Arrays;public class MinTest {public static void main(String[] args) {Integer[] oldArray = new Integer[] {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};System.out.println("原始:" + Arrays.toString(oldArray));Integer[] newArray = new Integer[oldArray.length];for (int i = 0; i < oldArray.length; i++) {siftUpComparable(i, oldArray[i], newArray);System.out.println("第" + i + ":" + Arrays.toString(newArray));}}private static <T> void siftUpComparable(int k, T x, Object[] array) {Comparable<? super T> key = (Comparable<? super T>) x;while (k > 0) {int parent = (k - 1) >>> 1;Object e = array[parent];if (key.compareTo((T) e) >= 0)break;array[k] = e;k = parent;}array[k] = key;}}

执行结果：

原始:[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
第0:[10, null, null, null, null, null, null, null, null, null]
第1:[9, 10, null, null, null, null, null, null, null, null]
第2:[8, 10, 9, null, null, null, null, null, null, null]
第3:[7, 8, 9, 10, null, null, null, null, null, null]
第4:[6, 7, 9, 10, 8, null, null, null, null, null]
第5:[5, 7, 6, 10, 8, 9, null, null, null, null]
第6:[4, 7, 5, 10, 8, 9, 6, null, null, null]
第7:[3, 4, 5, 7, 8, 9, 6, 10, null, null]
第8:[2, 3, 5, 4, 8, 9, 6, 10, 7, null]
第9:[1, 2, 5, 4, 3, 9, 6, 10, 7, 8]

这篇关于JDK8中关于最小堆的实现（PriorityBlockingQueue）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---