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.max;
  8.  
  9. class MaxBinaryHeap<T extends Comparable<? super T>>
  10.         extends AbstractQueue<T> {
  11.     private static final int MIN_HEIGHT = 1;
  12.  
  13.     private T[] data;
  14.     // the number of elements stored in the queue (not including the
  15.     // 0-th null element) and simultaneously the index of the
  16.     // last non-null element in the `data` array
  17.     private int size;
  18.  
  19.     @SuppressWarnings("unchecked")
  20.     public MaxBinaryHeap() {
  21.         data = (T[]) new Comparable<?>[1 << MIN_HEIGHT];
  22.     }
  23.  
  24.     @SuppressWarnings("unchecked")
  25.     private MaxBinaryHeap(T[] data, int size) {
  26.         T[] newData = (T[]) new Comparable<?>[data.length];
  27.         System.arraycopy(data, 0, newData, 0, data.length);
  28.         this.data = newData;
  29.         this.size = size;
  30.     }
  31.  
  32.     @Override
  33.     public boolean offer(T value) {
  34.         grow(1);
  35.         // put the element at the end of the heap
  36.         // and swim it to the proper position
  37.         size++;
  38.         data[size] = value;
  39.         swim(size);
  40.         return true;
  41.     }
  42.  
  43.     @Override
  44.     public T poll() {
  45.         if (size == 0) {
  46.             return null;
  47.         }
  48.         // swap the first and the last elements
  49.         swap(data, 1, size);
  50.         T value = data[size];
  51.         data[size] = null;
  52.         size--;
  53.         // and lower the element that is out of place
  54.         // to the proper position
  55.         if (size > 1) {
  56.             sink(1);
  57.         }
  58.  
  59.         shrink();
  60.         return value;
  61.     }
  62.  
  63.     @Override
  64.     public T peek() {
  65.         if (size == 0) {
  66.             return null;
  67.         }
  68.         return data[1];
  69.     }
  70.  
  71.     @Override
  72.     public int size() {
  73.         return size;
  74.     }
  75.  
  76.     @Override
  77.     public boolean isEmpty() {
  78.         return size == 0;
  79.     }
  80.  
  81.     @Override
  82.     public Iterator<T> iterator() {
  83.         return new QueueIterator();
  84.     }
  85.  
  86.     /**
  87.      * In case the key of the element at the position `index` is
  88.      * too large this method swims the specified element up to
  89.      * its proper position, simultaniously maintaining the heap
  90.      * ordering.
  91.      */
  92.     private void swim(int index) {
  93.         assert index >= 1 && index <= size;
  94.  
  95.         while (index > 1 && less(data, index / 2, index)) {
  96.             swap(data, index / 2, index);
  97.             index /= 2;
  98.         }
  99.     }
  100.  
  101.     /**
  102.      * In case the key of the element at the position `index` is too
  103.      * large this method sinks the specified element down to its place.
  104.      */
  105.     private void sink(int index) {
  106.         assert index >= 1 && index <= size;
  107.  
  108.         while (2 * index <= size) {
  109.             // choose the max child to preserve the heap oredering
  110.             int iMaxChild = 2 * index;
  111.             if (iMaxChild + 1 <= size 
  112.                     && less(data, iMaxChild, iMaxChild + 1)) {
  113.                 iMaxChild = iMaxChild + 1;
  114.             }
  115.             // data[index] >= data[iMaxChild]
  116.             if (!less(data, index, iMaxChild)) {
  117.                 break;
  118.             }
  119.             swap(data, index, iMaxChild);
  120.             index = iMaxChild;
  121.         }
  122.     }
  123.  
  124.     /**
  125.      * Updates the length of the `data` array, so that it could fit
  126.      * `by` more added elements
  127.      */
  128.     private void grow(int by) {
  129.         if (size + by + 1 > data.length) {
  130.             // the exact size of the array needed to store all elements:
  131.             // size = 2^(floor(lgN) + 1) - 1
  132.             // +1 for the 0-th null element
  133.             int newSize = 1 << log2(size + by) + 1;
  134.             reallocate(max(1 << MIN_HEIGHT, newSize));
  135.         }
  136.     }
  137.  
  138.     /**
  139.      * Shrinks the array in size, so that it would be approximately
  140.      * 50% full.
  141.      */
  142.     private void shrink() {
  143.         int newSize = 1 << log2(size) + 1;
  144.         if (size + 1 <= data.length / 4) {
  145.             reallocate(max(1 << MIN_HEIGHT, newSize));
  146.         }
  147.     }
  148.  
  149.     /**
  150.      * Copies the meaningful contents of the `data` array into a
  151.      * new array of size `newSize`.
  152.      */
  153.     @SuppressWarnings("unchecked")
  154.     private void reallocate(int newSize) {
  155.         assert newSize >= size;
  156.  
  157.         T[] newData = (T[]) new Comparable<?>[newSize];
  158.         System.arraycopy(data, 0, newData, 0, size + 1);
  159.         data = (T[]) newData;
  160.     }
  161.  
  162.     private class QueueIterator implements Iterator<T> {
  163.         private final MaxBinaryHeap<T> pqCopy;
  164.  
  165.         public QueueIterator() {
  166.             pqCopy = new MaxBinaryHeap<>(data, size);
  167.         }
  168.  
  169.         @Override
  170.         public boolean hasNext() {
  171.             return !pqCopy.isEmpty();
  172.         }
  173.  
  174.         @Override
  175.         public T next() {
  176.             if (!hasNext()) {
  177.                 throw new NoSuchElementException("The queue is empty.");
  178.             }
  179.             return pqCopy.remove();
  180.         }
  181.     }
  182.  
  183.     private static void swap(Object[] array, int i, int j) {
  184.         assert rangeCheck(array, i) && rangeCheck(array, j);
  185.  
  186.         if (i != j) {
  187.             Object swap = array[i];
  188.             array[i] = array[j];
  189.             array[j] = swap;
  190.         }
  191.     }
  192.  
  193.     private static <T extends Comparable<? super T>>
  194.             boolean less(T[] array, int i, int j) {
  195.         assert rangeCheck(array, i) && rangeCheck(array, j);
  196.  
  197.         return array[i].compareTo(array[j]) < 0;
  198.     }
  199.  
  200.     private static boolean rangeCheck(Object[] array, int i) {
  201.         return array != null && i >= 0 && i < array.length;
  202.     }
  203.  
  204.     /**
  205.      * Calculates the floored logarithm base 2 of a given integer
  206.      * in constant time using the bitwise operations.
  207.      */
  208.     private static int log2(int value) {
  209.         int log = 0;
  210.         // basically this algorithm counts the number of leading zeros,
  211.         // but subtracted from the sizeof(int)
  212.  
  213.         // this covers the case when there are 1's on the left side
  214.         // so the result is definitely greater than 16
  215.         if ((value & 0xFFFF0000) != 0) {
  216.             value >>>= 16;
  217.             log += 16;
  218.         }
  219.         if ((value & 0xFF00) != 0) {
  220.             value >>>= 8;
  221.             log += 8;
  222.         }
  223.         if ((value & 0xF0) != 0) {
  224.             value >>>= 4;
  225.             log += 4;
  226.         }
  227.         if ((value & 0b1100) != 0) {
  228.             value >>>= 2;
  229.             log += 2;
  230.         }
  231.         if ((value & 0b10) != 0) {
  232.             value >>>= 1;
  233.             log += 1;
  234.         }
  235.         return log;
  236.     }
  237.  
  238.     public static void main(String[] args) {
  239.     	MaxBinaryHeap<Integer> heap = new MaxBinaryHeap<>();
  240.     	Random random = new Random();
  241.     	for (int i = 0; i < 10; i++) {
  242.     		heap.offer(random.nextInt(100));
  243.     	}
  244.     	for (int i = 0; i < 10; i++) {
  245.     		System.out.printf(" %d", heap.poll());
  246.     	}
  247.     }
  248. }
Success #stdin #stdout 0.08s 34276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 97 74 70 65 53 45 31 28 23 1
https://ideone.com/ETkMD0
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!