courtneythurston

Untitled

Mar 4th, 2021
654
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.       // Write your code here.
  16.     }
  17.  
  18.     public void siftDown(int currentIdx, int endIdx, List<Integer> heap) {
  19.       // basically ok theres a hole at root, gotta fill with a child
  20.             // then gotta fill that node's child with a child etc etc
  21.             int temp;
  22.             while (endIdx <= currentIdx){
  23.                 if ((heap[currentIdx] < heap[2 * currentIdx + 1]) && (heap[currentIdx] < heap[2 * currentIdx + 2])){
  24.                     break;
  25.                 }
  26.                 if ((heap[2 * currentIdx + 1] <= endIndx) && (heap[2 * currentIdx + 2] <= endIdx)){
  27.                     if (heap[2] currentIdx + 1] < heap[2 * currentIfx + 2]) {
  28.                         temp = heap[currentIdx];
  29.                         heap[currentIdx] = heap[2 * currentIdx + 1];
  30.                         heap[2 * currentIdx + 1] = temp;
  31.                         currentIfx = heap[2 * currentIdx + 1];
  32.                     }
  33.                     else if (heap[2 * currentIfx + 2] < heap[2 * currentIdx + 1]){
  34.                         temp = heap[currentIdx];
  35.                         heap[currentIdx] = heap[2 * currentIdx + 2];
  36.                         heap[2 * currentIdx + 2] = temp;
  37.                         currentIfx = heap[2 * currentIdx + 2];
  38.                     }
  39.                 }
  40.             }
  41.     }
  42.  
  43.     public void siftUp(int currentIdx, List<Integer> heap) {
  44.             int siftValue = heap[heap.length - 1];
  45.             for (int currentIdx = heap.length - 1; currentIdx > 0; Math.floor((currentIdx - 1)/2)) {
  46.                 if (siftValue < heap[Math.floor((currentIdx-1)/2)]){
  47.                     int tempValue = heap[Math.floor((currentIdx-1)/2)];
  48.                     heap[Math.floor((currentIdx-1)/2)] = siftValue;
  49.                     tempValue = heap[currentIdx];
  50.                 }
  51.             }
  52.     }
  53.  
  54.     public int peek() {
  55.       if (heap[0] != null){
  56.                 return heap[0];
  57.             }
  58.       return -1;
  59.     }
  60.  
  61.     public int remove() {
  62.       // Swap last element with root, resize to destroy old root, sift down
  63.             if ((heap[0] != null) && (heap.length => 2)){
  64.                 int tempValue = heap[0];
  65.                 heap[0] = heap[heap.length-1];
  66.                 heap[heap.length-1] = tempValue;
  67.                 heap.subList(heap.length - 1, heap.length).clear();
  68.                 siftDown(0, heap.length-1, heap);
  69.                 return tempValue;
  70.             }
  71.       return -1;
  72.     }
  73.  
  74.     public void insert(int value) {
  75.             heap.add(value);
  76.             siftUp(value);
  77.         }
  78.   }
  79. }
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.

×