SHARE
TWEET

Untitled

a guest Jun 26th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public final class MaxHeap<T extends Comparable<? super T>> implements MaxHeapInterface<T>
  2. {
  3. private T[] heap;
  4. private int lastIndex;
  5. private boolean initialized = false;
  6. private static final int DEFAULT_CAPACITY = 25;
  7. private static final int MAX_CAPACITY = 10000;
  8.  
  9. int swaps=0;
  10.  
  11. public MaxHeap() {
  12.     this(DEFAULT_CAPACITY);
  13. }
  14.  
  15. public MaxHeap(int initialCapacity) {
  16.     if (initialCapacity < DEFAULT_CAPACITY)
  17.         initialCapacity = DEFAULT_CAPACITY;
  18.     else
  19.         checkCapacity(initialCapacity);
  20.  
  21.     @SuppressWarnings("unchecked")
  22.     T[] tempHeap = (T[]) new Comparable[initialCapacity + 1];
  23.     heap = tempHeap;
  24.     lastIndex = 0;
  25.     initialized = true;
  26. }
  27.  
  28. public T getMax() {
  29.     checkInitialization();
  30.     T root = null;
  31.     if (!isEmpty())
  32.         root = heap[1];
  33.     return root;
  34. }
  35.  
  36. public boolean isEmpty() {
  37.     return lastIndex < 1;
  38. }
  39.  
  40. public int getSize() {
  41.     return lastIndex;
  42. }
  43.  
  44. public void clear() {
  45.     checkInitialization();
  46.     while (lastIndex > -1) {
  47.         heap[lastIndex] = null;
  48.         lastIndex--;
  49.     }
  50.     lastIndex = 0;
  51. }
  52.  
  53. public void add(T newEntry) {
  54.     checkInitialization();
  55.     int newIndex = lastIndex + 1;
  56.     int parentIndex = newIndex / 2;
  57.     while ((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0) {
  58.         heap[newIndex] = heap[parentIndex];
  59.         newIndex = parentIndex;
  60.         parentIndex = newIndex / 2;
  61.         swaps++;
  62.     }
  63.     heap[newIndex] = newEntry;
  64.     lastIndex++;
  65.     ensureCapacity();
  66. }
  67. public int getSwaps()
  68. {
  69.     return swaps;
  70. }
  71. public T removeMax() {
  72.     checkInitialization();
  73.     T root = null;
  74.     if (!isEmpty()) {
  75.         root = heap[1];
  76.         heap[1] = heap[lastIndex];
  77.         lastIndex--;
  78.         reheap(1);
  79.     }
  80.     return root;
  81. }
  82. private void reheap(int rootIndex) {
  83.     boolean done = false;
  84.     T orphan = heap[rootIndex];
  85.     int leftChildIndex = 2 * rootIndex;
  86.     while (!done && (leftChildIndex <= lastIndex)) {
  87.         int largerChildIndex = leftChildIndex;
  88.         int rightChildIndex = leftChildIndex + 1;
  89.         if ((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0) {
  90.             largerChildIndex = rightChildIndex;
  91.         }
  92.         if (orphan.compareTo(heap[largerChildIndex]) < 0) {
  93.             heap[rootIndex] = heap[largerChildIndex];
  94.             rootIndex = largerChildIndex;
  95.             leftChildIndex = 2 * rootIndex;
  96.             swaps++;
  97.         } else
  98.             done = true;
  99.     }
  100.     heap[rootIndex] = orphan;
  101.  
  102. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top