courtneythurston

Untitled

Mar 5th, 2021
711
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. // Do not edit the class below except for the buildHeap,
  4. // siftDown, siftUp, peek, remove, and insert methods.
  5. // Feel free to add new properties and methods to the class.
  6. class Program {
  7.   static class MinHeap {
  8.     List<Integer> heap = new ArrayList<Integer>();
  9.  
  10.     public MinHeap(List<Integer> array) {
  11.       heap = buildHeap(array);
  12.     }
  13.  
  14.     public List<Integer> buildHeap(List<Integer> array) {
  15.       for (int i=array.size()-1; i>=0; i--){
  16.                 siftDown(i, array.size()-1, array);
  17.             }
  18.             return array;
  19.     }
  20.  
  21.     public void siftDown(int currentIdx, int endIdx, List<Integer> heap) {
  22.       // basically ok theres a hole at root, gotta fill with a child
  23.             // then gotta fill that node's child with a child etc etc
  24.             int temp;
  25.             int leftChild;
  26.             int rightChild;
  27.             while (endIdx <= currentIdx){
  28.                 if ((heap.get(currentIdx) < heap.get(2 * currentIdx + 1)) && (heap.get(currentIdx) < heap.get(2 * currentIdx + 2))){
  29.                     break;
  30.                 }
  31.                 if ((heap.get(2 * currentIdx + 1) <= endIdx)){
  32.                     temp = heap.get(currentIdx);
  33.                     leftChild = heap.get(2 * currentIdx + 1);
  34.                     (heap.get(currentIdx)).set(leftChild);
  35.                     heap.get(2 * currentIdx + 1) = temp;
  36.                     currentIfx = heap.get(2 * currentIdx + 1);
  37.                 }
  38.                 if ((heap.get(2 * currentIdx + 1) <= endIdx) && (heap.get(2 * currentIdx + 2) <= endIdx)){
  39.                     if (heap.get(2 * currentIdx + 1) < heap.get(2 * currentIdx + 2)) {
  40.                         temp = heap.get(currentIdx);
  41.                         heap.get(currentIdx) = heap.get(2 * currentIdx + 1);
  42.                         heap.get(2 * currentIdx + 1) = temp;
  43.                         currentIfx = heap.get(2 * currentIdx + 1);
  44.                     }
  45.                     else if (heap.get(2 * currentIfx + 2) < heap.get(2 * currentIdx + 1)){
  46.                         temp = heap.get(currentIdx);
  47.                         heap.get(currentIdx) = heap.get(2 * currentIdx + 2);
  48.                         heap.get(2 * currentIdx + 2) = temp;
  49.                         currentIfx = heap.get(2 * currentIdx + 2);
  50.                     }
  51.                 }
  52.             }
  53.     }
  54.  
  55.     public void siftUp(int currentIdx, List<Integer> heap) {
  56.             int siftValue = heap.get(heap.size() - 1);
  57.             for (int currentIdx = heap.size() - 1; currentIdx > 0; currentIdx--) {
  58.                 if (siftValue < heap.get((currentIdx-1)/2)){
  59.                     int tempValue = heap.get((currentIdx-1)/2);
  60.                     heap.get((currentIdx-1)/2) = siftValue;
  61.                     tempValue = heap.get(currentIdx);
  62.                 }
  63.             }
  64.     }
  65.  
  66.     public int peek() {
  67.       if (heap.get(0) != null){
  68.                 return heap.get(0);
  69.             }
  70.       return -1;
  71.     }
  72.  
  73.     public int remove() {
  74.       // Swap last element with root, resize to destroy old root, sift down
  75.             int tempValue;
  76.             if (heap.size() == 1){
  77.                 tempValue = heap.get(0);
  78.                 heap.subList(0, heap.size()).clear();
  79.                 return tempValue;
  80.             }
  81.             if (heap.size() >= 2){
  82.                 tempValue = heap.get(0);
  83.                 heap.get(0) = heap.get(heap.size()-1);
  84.                 heap.get(heap.size()-1) = tempValue;
  85.                 heap.subList(heap.size() - 1, heap.size()).clear();
  86.                 siftDown(0, heap.size()-1, heap);
  87.                 return tempValue;
  88.             }
  89.       return -1;
  90.     }
  91.  
  92.     public void insert(int value) {
  93.             heap.add(value);
  94.             siftUp(heap.size()-1, heap); // is this right?
  95.         }
  96.   }
  97. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×