fork download
copy 
  1. import java.util.AbstractQueue;
  2. import java.util.Iterator;
  3. import java.util.Random;
  4.  
  5. import java.util.NoSuchElementException;
  6.  
  7. import static java.lang.Math.min;
  8. import static java.lang.Math.max;
  9.  
  10. class MaxDaryHeap<T extends Comparable<? super T>>
  11.         extends AbstractQueue<T> {
  12.     private static final int MIN_HEIGHT = 1;
  13.  
  14.     // unlike the binary heap implementation this d-ary heap
  15.     // does not add an additional null element on the 0-th place
  16.     // in the array, thus, the greatest element of the queue is
  17.     // stored in the data[0]
  18.     private T[] data;
  19.     private int size;
  20.     // the arity of the heap (how many children does each node have)
  21.     private final int d;
  22.  
  23.     /**
  24.      * Create a d-ary heap with arity {@code d}.
  25.      * @throws  IllegalArgumentException in case the arity {@code d} is
  26.      *          less than 2.
  27.      */
  28.     @SuppressWarnings("unchecked")
  29.     public MaxDaryHeap(int d) {
  30.     	if (d < 2) {
  31.     		throw new IllegalArgumentException(String.format("Expected: d >= 2."
  32.     			+ " Got: d = %d.", d));
  33.     	}
  34.         this.d = d;
  35.         // size = d^0 + d^1 + ... + d^h = (d^(h + 1) - 1) / (d - 1)
  36.         int dataLength = pow(d, MIN_HEIGHT + 1) / (d - 1);
  37.         data = (T[]) new Comparable<?>[dataLength];
  38.         size = 0;
  39.     }
  40.  
  41.     @SuppressWarnings("unchecked")
  42.     private MaxDaryHeap(T[] data, int size, int d) {
  43.         T[] copiedData = (T[]) new Comparable<?>[data.length];
  44.         System.arraycopy(data, 0, copiedData, 0, data.length);
  45.         this.data = copiedData;
  46.         this.size = size;
  47.         this.d = d;
  48.     }
  49.  
  50.     /**
  51.      * Inserts the specified value into the queue.
  52.      * @throws  NullPointerException in case the {@code null} element
  53.      *          is inserted.
  54.      */
  55.     @Override
  56.     public boolean offer(T value) {
  57.         if (value == null) {
  58.             throw new NullPointerException(
  59.                 "Null elements are not allowed"
  60.             );
  61.         }
  62.         grow(1);
  63.         size++;
  64.         data[size - 1] = value;
  65.         swim(size - 1);
  66.         return true;
  67.     }
  68.  
  69.     @Override
  70.     /**
  71.      * Retrieves but does not remove the max element stored in the queue.
  72.      */
  73.     public T peek() {
  74.         if (size == 0) {
  75.             throw new NoSuchElementException("The heap is empty");
  76.         }
  77.         return data[0];
  78.     }
  79.  
  80.     @Override
  81.     /**
  82.      * Retrieves and removes the max element stored in the queue.
  83.      */
  84.     public T poll() {
  85.         if (size == 0) {
  86.             throw new NoSuchElementException("The heap is empty");
  87.         }
  88.         T value = data[0];
  89.         data[0] = null;
  90.         size--;
  91.  
  92.         if (size > 0) {
  93.             data[0] = data[size];
  94.             sink(0);
  95.         }
  96.  
  97.         // `true` for only a single element removed from the queue
  98.         shrink(true);
  99.         return value;
  100.     }
  101.  
  102.     @Override
  103.     public boolean isEmpty() {
  104.         return size == 0;
  105.     }
  106.  
  107.     @Override
  108.     public int size() {
  109.         return size;
  110.     }
  111.  
  112.     @Override
  113.     public Iterator<T> iterator() {
  114.         return new QueueIterator();
  115.     }
  116.  
  117.     private void swim(int i) {
  118.         assert i >= 0 && i < size;
  119.  
  120.         while (i > 0 && less(data, (i - 1) / d, i)) {
  121.             swap(data, (i - 1) / d, i);
  122.             i = (i - 1) / d;
  123.         }
  124.     }
  125.  
  126.     private void sink(int index) {
  127.         assert index >= 0 && index < size;
  128.  
  129.         while (index * d + 1 < size) {
  130.             int iMaxChild = index * d + 1;
  131.             int upperBound = min(size, (index + 1) * d + 1);
  132.             for (int i = 2; index * d + i < upperBound; i++) {
  133.                 if (less(data, iMaxChild, index * d + i)) {
  134.                     iMaxChild = index * d + i;
  135.                 }
  136.             }
  137.             if (!less(data, index, iMaxChild)) {
  138.                 break;
  139.             }
  140.             swap(data, index, iMaxChild);
  141.             index = iMaxChild;
  142.         }
  143.     }
  144.  
  145.     // the `by` argument could be useful if we'd implement a method
  146.     // that adds several elements to the queue in a row, not just one
  147.     private void grow(int by) {
  148.         assert by > 0;
  149.  
  150.         if (size + by > data.length) {
  151.             if (by == 1) {
  152.                 reallocate(data.length * d + 1);
  153.             } else {
  154.                 reallocate(getFittingArraySize(size + by, d));
  155.             }
  156.         }
  157.     }
  158.  
  159.     private void shrink(boolean oneElementRemoved) {
  160.         if (size <= data.length / (d * d)) {
  161.             int minSize = pow(d, MIN_HEIGHT + 1) / (d - 1);
  162.             if (oneElementRemoved) {
  163.                 reallocate(max(data.length / d, minSize));
  164.             } else {
  165.                 reallocate(max(getFittingArraySize(size, d), minSize));
  166.             }
  167.         }
  168.     }
  169.  
  170.     @SuppressWarnings("unchecked")
  171.     private void reallocate(int newSize) {
  172.         assert newSize >= size;
  173.  
  174.         T[] newData = (T[]) new Comparable<?>[newSize];
  175.         System.arraycopy(data, 0, newData, 0, size);
  176.         data = newData;
  177.     }
  178.  
  179.     private class QueueIterator implements Iterator<T> {
  180.         private final MaxDaryHeap<T> pqCopy;
  181.  
  182.         public QueueIterator() {
  183.             pqCopy = new MaxDaryHeap<>(data, size, d);
  184.         }
  185.  
  186.         @Override
  187.         public boolean hasNext() {
  188.             return !pqCopy.isEmpty();
  189.         }
  190.  
  191.         @Override
  192.         public T next() {
  193.             if (!hasNext()) {
  194.                 throw new NoSuchElementException("The queue is empty.");
  195.             }
  196.             return pqCopy.poll();
  197.         }
  198.     }
  199.  
  200.     private static int getFittingArraySize(int size, int d) {
  201.         // size + by = (d^(height + 1) - 1) / (d - 1)
  202.         // => height = floor[log_d((size + by) * (d - 1))] - 1
  203.         int height = log(d, size * (d - 1)) - 1;
  204.         int arrayLength = (pow(d, height + 1) - 1) / (d - 1);
  205.         return arrayLength;
  206.     }
  207.  
  208.     private static <T extends Comparable<? super T>>
  209.             boolean less(T[] array, int i, int j) {
  210.         assert rangeCheck(array, i) && rangeCheck(array, j);
  211.  
  212.         return array[i].compareTo(array[j]) < 0;
  213.     }
  214.  
  215.     private static void swap(Object[] array, int i, int j) {
  216.         assert rangeCheck(array, i) && rangeCheck(array, j)
  217.             : String.format("i = %d, j = %d, len(array) = %d",
  218.             i, j, array.length);
  219.  
  220.         Object swap = array[i];
  221.         array[i] = array[j];
  222.         array[j] = swap;
  223.     }
  224.  
  225.     private static boolean rangeCheck(Object[] array, int i) {
  226.         return array != null && i >= 0 && i < array.length;
  227.     }
  228.  
  229.     /**
  230.      * Calculates the x^n value.
  231.      */
  232.     private static int pow(int x, int n) {
  233.         assert n >= 0;
  234.  
  235.         int result = 1;
  236.         for (int i = 0; i < n; i++) {
  237.             result *= x;
  238.         }
  239.         return result;
  240.     }
  241.  
  242.     /**
  243.      * Calculates the floor(log_base(argument)) value.
  244.      */
  245.     private static int log(int base, int argument) {
  246.         assert argument > 0 && base > 1;
  247.  
  248.         int log = 0;
  249.         int intermediate = 1;
  250.         while (intermediate <= argument) {
  251.             intermediate *= base;
  252.             log++;
  253.         }
  254.         return log;
  255.     }
  256.  
  257.     public static void main(String[] args) {
  258.         MaxDaryHeap<Integer> heap = new MaxDaryHeap<>(5);
  259.     	Random random = new Random();
  260.     	for (int i = 0; i < 100; i++) {
  261.     		heap.offer(random.nextInt(10000));
  262.     	}
  263.     	for (int i = 0; i < 100; i++) {
  264.     		System.out.printf(" %d", heap.poll());
  265.     	}
  266.     }
  267. }
Success #stdin #stdout 0.1s 34492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 9857 9761 9665 9636 9494 9281 9259 9224 9076 8962 8887 8852 8826 8545 8477 8386 8370 8368 8222 8222 8214 8147 8075 7795 7654 7550 7390 7385 7276 7226 7011 7005 6766 6671 6565 6371 6361 6045 5619 5499 5375 5233 4992 4930 4911 4902 4899 4787 4779 4692 4515 4271 4268 4235 4179 4156 3693 3439 3138 3032 3015 2725 2725 2565 2542 2517 2347 2322 2312 2297 2226 2014 1988 1524 1521 1369 1277 1276 1208 1170 1110 1077 941 734 726 699 687 528 448 397 379 375 352 339 317 313 228 183 162 67
https://ideone.com/ps4Xb1
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!