import java.util.Arrays;import java.util.concurrent.ThreadLocalRandom;public abstract class Heap<T extends Comparable<T>> {private static final Comparable<?>[] empty = new Comparable[0];@SuppressWarnings("unchecked")protected T[] objs = (T[])empty;protected int size;public int size() {return size;}public void clear() {Arrays.fill(objs, 0, size, null);size = 0;}public T get(int i) {return objs[i];}public abstract void push(T obj);public abstract T pop();static void ASSERT(boolean b) {if (!b)throw new AssertionError();}static void testN(Heap<Integer> h, int n) {ThreadLocalRandom r = ThreadLocalRandom.current();int aa = 0;for (int i = 0; i < n; i++) {int a = r.nextInt(n);h.push(a);aa += a;}ASSERT(h.size() == n);int a = -1, bb = 0;for (int i = 0; i < n; i++) {int b = h.pop();ASSERT(a <= b);a = b;bb += b;}ASSERT(h.size() == 0);ASSERT(h.pop() == null);ASSERT(aa == bb);for (int i = 0; i < n; i++)ASSERT(h.get(i) == null);}static void test(Heap<Integer> h) {ASSERT(h.size() >= 0);h.clear();ASSERT(h.size() == 0);ASSERT(h.pop() == null);for (int n = 0; n <= 5; n++)testN(h, n);for (int n = 10; n <= 1000000; n *= 10)testN(h, n);System.out.format("test %s OK!\n", h.getClass().getSimpleName());}static void benchmarkN(Heap<Integer> h, int n) {ThreadLocalRandom r = ThreadLocalRandom.current();long t = System.nanoTime();for (int i = 0; i < n; i++)h.push(r.nextInt(n));int a = 0;for (int i = 0; i < n; i++)a += h.pop();t = System.nanoTime() - t;System.out.format("%10s(%7d):%10d ns, %d\n", h.getClass().getSimpleName(), n, t, a);}static void benchmark(Heap<Integer> h) {h.clear();for (int n = 10; n <= 1000000; n *= 10)benchmarkN(h, n);}public static void main(String[] ignoredArgs) {BinHeap<Integer> bh = new BinHeap<>();QuadHeap<Integer> qh = new QuadHeap<>();OctHeap<Integer> oh = new OctHeap<>();test(bh);test(qh);test(oh);System.out.println("---");for (int i = 0; i < 5; i++) {benchmark(bh);benchmark(qh);benchmark(oh);System.out.println("---");}}}// [0 1 2 3 4 5 6 7 ...]// [R R0 R1 R00 R01 R10 R11 R000 ...]// parentIndex = (childIndex-1)/2// childIndex = parentIndex*2+(1|2)class BinHeap<T extends Comparable<T>> extends Heap<T> {@Overridepublic void push(T obj) {if (obj == null)throw new NullPointerException();T[] os = objs;int i = size;if (i == os.length)objs = os = Arrays.copyOf(os, Math.max(i * 2, 16));size = i + 1;while (i > 0) { // sift upint j = (i - 1) >> 1;T po = os[j];if (obj.compareTo(po) >= 0)break;os[i] = po;i = j;}os[i] = obj;}@Overridepublic T pop() {int n = size;if (n == 0)return null;T[] os = objs;T r = os[0], obj = os[--n];os[n] = null;size = n;if (n > 0) {int i = 0;for (T c, d; ; ) { // sift downint j = i * 2 + 1, k = j + 1;if (k < n) { // full childrenif ((c = os[j]).compareTo(d = os[k]) >= 0) {c = d;j = k;}} else if (j < n) // part of childrenc = os[j];else // no childbreak;if (c.compareTo(obj) >= 0)break;os[i] = c;i = j;}os[i] = obj;}return r;}}// [0 1 2 3 4 5 6 7 8 9 ...]// [R R0 R1 R2 R3 R00 R01 R02 R03 R10 ...]// parentIndex = (childIndex-1)/4// childIndex = parentIndex*4+(1|2|3|4)class QuadHeap<T extends Comparable<T>> extends Heap<T> {@Overridepublic void push(T obj) {if (obj == null)throw new NullPointerException();T[] os = objs;int i = size;if (i == os.length)objs = os = Arrays.copyOf(os, Math.max(i * 2, 16));size = i + 1;while (i > 0) { // sift upint j = (i - 1) >> 2;T po = os[j];if (obj.compareTo(po) >= 0)break;os[i] = po;i = j;}os[i] = obj;}@Overridepublic T pop() {int n = size;if (n == 0)return null;T[] os = objs;T r = os[0], obj = os[--n];os[n] = null;size = n;if (n > 0) {int i = 0;for (T c, d; ; ) { // sift downint j = i * 4 + 1, k;if (j + 3 < n) { // full childrenc = os[j];if (c.compareTo(d = os[k = j + 1]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}} else if (j < n) { // part of childrenc = os[j];if ((k = j + 1) < n) {if (c.compareTo(d = os[k]) >= 0) {c = d;j = k;}if (++k < n && c.compareTo(d = os[k]) >= 0) {c = d;j = k;}}} else // no childbreak;if (c.compareTo(obj) >= 0)break;os[i] = c;i = j;}os[i] = obj;}return r;}}// [0 1 2 3 4 5 6 7 8 9 ...]// [R R0 R1 R2 R3 R4 R5 R6 R7 R00 ...]// parentIndex = (childIndex-1)/8// childIndex = parentIndex*8+(1|2|3|4|5|6|7|8)class OctHeap<T extends Comparable<T>> extends Heap<T> {@Overridepublic void push(T obj) {if (obj == null)throw new NullPointerException();T[] os = objs;int i = size;if (i == os.length)objs = os = Arrays.copyOf(os, Math.max(i * 2, 16));size = i + 1;while (i > 0) { // sift upint j = (i - 1) >> 3;T po = os[j];if (obj.compareTo(po) >= 0)break;os[i] = po;i = j;}os[i] = obj;}@Overridepublic T pop() {int n = size;if (n == 0)return null;T[] os = objs;T r = os[0], obj = os[--n];os[n] = null;size = n;if (n > 0) {int i = 0;for (T c, d; ; ) { // sift downint j = i * 8 + 1, k;if (j + 7 < n) { // full childrenc = os[j];if (c.compareTo(d = os[k = j + 1]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}if (c.compareTo(d = os[++k]) >= 0) {c = d;j = k;}} else if (j < n) { // part of childrenc = os[j];if ((k = j + 1) < n) {if (c.compareTo(d = os[k]) >= 0) {c = d;j = k;}if (++k < n) {if (c.compareTo(d = os[k]) >= 0) {c = d;j = k;}if (++k < n) {if (c.compareTo(d = os[k]) >= 0) {c = d;j = k;}if (++k < n) {if (c.compareTo(d = os[k]) >= 0) {c = d;j = k;}if (++k < n) {if (c.compareTo(d = os[k]) >= 0) {c = d;j = k;}if (++k < n && c.compareTo(d = os[k]) >= 0) {c = d;j = k;}}}}}}} else // no childbreak;if (c.compareTo(obj) >= 0)break;os[i] = c;i = j;}os[i] = obj;}return r;}}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。