brainuser5705

heap implementation in java

Jun 17th, 2022 (edited)
768
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.40 KB | None
  1. package Heaps;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. /**
  6.  * Array implementation of Heap data structure and methods
  7.  * @author ---
  8.  */
  9. public class HeapArray<T extends Comparable<T>>{
  10.  
  11.     /**
  12.      * The array containing the element in heap order.
  13.      * It is an ArrayList to allow dynamic insertion.
  14.      */
  15.     private ArrayList<T> array;
  16.     /**
  17.      * This value is mutplied with the return of compareTo() between the two objects.
  18.      * 1 if min heap, -1 if max heap
  19.      */
  20.     int compareValue;
  21.  
  22.     /**
  23.      * Constructs a heap array and determines if min heap or max heap by setting {@code compareValue}
  24.      * @param isMin true if min heap, false if max heap
  25.      */
  26.     public HeapArray(boolean isMin){
  27.         array = new ArrayList<>();
  28.         compareValue = isMin ? 1 : -1;
  29.     }
  30.  
  31.     /**
  32.      * Insert value into heap by appending to array and calls {@link shiftUp()} to heapify
  33.      * @param value
  34.      */
  35.     public void insert(T value){
  36.         array.add(value);
  37.         int size = array.size() - 1;
  38.         if (size != 0)
  39.             shiftUp(size);
  40.     }
  41.  
  42.     /**
  43.      * If the element is greater (max heap) or less (min heap) than the parent, then swap indexes.
  44.      * This is recursively executed until condition fails.
  45.      * @param index the index to start shifting up from
  46.      */
  47.     private void shiftUp(int index){
  48.         int parentIndex = getParent(index);
  49.         T parentValue = array.get(parentIndex);
  50.         T currentValue = array.get(index);
  51.    
  52.         // comparator.compare(parentValue, currentValue) > 0
  53.         if(compareValue * parentValue.compareTo(currentValue) > 0){
  54.             swap(parentIndex, index);
  55.             shiftUp(parentIndex);
  56.         }
  57.     }
  58.  
  59.     /**
  60.      * Remove the maximum or minimum value of array , make last element the root, then calls {@link shiftDown()} to heapify
  61.      * @return the maximum value of array if max heap, the minimum value of array if min heap (note that these values are located at index 0)
  62.      */
  63.     public T remove(){
  64.        
  65.         int index = array.size() - 1;
  66.  
  67.         if (index >= 0){ // if not empty
  68.  
  69.             T value = array.get(0);
  70.             swap(0, index);
  71.             array.remove(index); // removes the original root value
  72.            
  73.             if (index > 0) // if not empty after removal in the previous line
  74.                 shiftDown(0);
  75.            
  76.             return value;
  77.         }
  78.        
  79.         return null;
  80.     }
  81.  
  82.     /**
  83.      * There are two conditions when shifting down from an index:
  84.      * 1) If only left child is present, if the element is greater (max heap) or less (min heap) then left child, then swap indexes.
  85.      * 2) If right child is present (note that this inherently means that left child is present), determine smallest element of the childs,
  86.      * if the element is greater (max heap) or less (min heap) then smallest child, then swap indexes.
  87.      *
  88.      * This is recursively executed until index has no child elements.
  89.      * @param index the index to start shifting down from
  90.      */
  91.     private void shiftDown(int index){
  92.  
  93.         int lastIndex = array.size() - 1;
  94.         int leftChildIndex = getLeftChild(index);
  95.         int rightChildIndex = getRightChild(index);
  96.        
  97.         // variable holding either leftChildIndex or rightChildIndex to swap
  98.         int swapIndex;
  99.         T leftChildValue, rightChildValue, switchValue, currentValue = array.get(index);
  100.  
  101.         // if there is a right index, there will be a left index inherently
  102.         if (rightChildIndex <= lastIndex){
  103.  
  104.             // determine which value is the least and should swap
  105.             leftChildValue = array.get(leftChildIndex);
  106.             rightChildValue = array.get(rightChildIndex);
  107.  
  108.             if (compareValue * leftChildValue.compareTo(rightChildValue) < 0){
  109.                 swapIndex = leftChildIndex;
  110.                 switchValue = leftChildValue;
  111.             }else{
  112.                 swapIndex = rightChildIndex;
  113.                 switchValue = rightChildValue;
  114.             }
  115.  
  116.             // determine if swap needed
  117.             if (compareValue * switchValue.compareTo(currentValue) < 0){
  118.                 swap(swapIndex, index);
  119.                 shiftDown(swapIndex);
  120.             }
  121.            
  122.         // there is no right child, then check if there is a left child
  123.         }else if (leftChildIndex <= lastIndex){
  124.  
  125.             leftChildValue = array.get(leftChildIndex);
  126.             if (compareValue * leftChildValue.compareTo(currentValue) < 0){
  127.                 swap(leftChildIndex, index);
  128.                 shiftDown(leftChildIndex);
  129.             }
  130.  
  131.         }
  132.     }
  133.  
  134.     /**
  135.      * Swaps the values at the two indexes.
  136.      * @param index1 one of the indexes
  137.      * @param index2 the other index
  138.      */
  139.     private void swap(int index1, int index2){
  140.         T temp = array.get(index1);
  141.         array.set(index1, array.get(index2));
  142.         array.set(index2, temp);
  143.     }
  144.  
  145.     /**
  146.      * Gets the parent of an index in a heap array
  147.      * @param index the index to get parent of
  148.      * @return the parent index of the index
  149.      */
  150.     private int getParent(int index){
  151.         return (index - 1) / 2;
  152.     }
  153.  
  154.     /**
  155.      * Gets the left child of an index in a heap array
  156.      * @param index the index to get left child of
  157.      * @return the left child index of the index
  158.      */
  159.     private int getLeftChild(int index){
  160.         return index * 2 + 1;
  161.     }
  162.  
  163.     /**
  164.      * Gets the right child of an index in a heap array
  165.      * @param index the index to get right child of
  166.      * @return the right child index of the index
  167.      */
  168.     private int getRightChild(int index){
  169.         return index * 2 + 2;
  170.     }
  171.  
  172.     /**
  173.      * Returns heap array in string representation.
  174.      */
  175.     public String toString(){
  176.         return array.toString();
  177.     }
  178.  
  179.     /**
  180.      * Main function containing tests.
  181.      * @param args none
  182.      */
  183.     public static void main(String args[]) {
  184.         final int NUM_SIZE = 5;
  185.  
  186.         // Testing min heap
  187.         System.out.println("Testing Min Heap");
  188.        
  189.         HeapArray<Integer> minHeap = new HeapArray<>(true);
  190.        
  191.         System.out.println("Heap: " + minHeap);
  192.  
  193.         for (int i = 0; i < NUM_SIZE; i++){
  194.             int randomValue = (int) (Math.random() * 100) + 0;
  195.             minHeap.insert(randomValue);
  196.             System.out.println("Adding " + randomValue);
  197.             System.out.println("Heap: " + minHeap);
  198.         }
  199.  
  200.         System.out.println("\n");
  201.  
  202.         for (int i = 0; i < NUM_SIZE; i++){
  203.             int value = minHeap.remove();
  204.             System.out.println("Removing " + value);
  205.             System.out.println("Heap: " + minHeap);
  206.         }
  207.  
  208.         // Testing max heap
  209.         System.out.println("\nTesting Max Heap");
  210.  
  211.         HeapArray<Integer> maxHeap = new HeapArray<>(false);
  212.  
  213.         System.out.println("Heap: " + maxHeap);
  214.  
  215.         for (int i = 0; i < NUM_SIZE; i++){
  216.             int randomValue = (int) (Math.random() * 100) + 0;
  217.             maxHeap.insert(randomValue);
  218.             System.out.println("Adding " + randomValue);
  219.             System.out.println("Heap: " + maxHeap);
  220.         }
  221.  
  222.         System.out.println("\n");
  223.  
  224.         for (int i = 0; i < NUM_SIZE; i++){
  225.             int value = maxHeap.remove();
  226.             System.out.println("Removing " + value);
  227.             System.out.println("Heap: " + maxHeap);
  228.         }
  229.     }
  230.  
  231. }
RAW Paste Data Copied