added heap data structureHEADmaster

1 files changed, 102 insertions, 0 deletions

diff --git a/Heap.java b/Heap.java
new file mode 100644
index 0000000..4f9b37f
--- /dev/null
+++ b/Heap.java
@@ -0,0 +1,102 @@
+import java.util.ArrayList;
+import java.lang.Math;
+
+public class Heap<T extends Comparable<T>> {
+    
+    private ArrayList<T> array = new ArrayList<>();
+
+    public Heap(){}
+
+    public Heap(ArrayList<T> sourceArr) {
+        array = sourceArr;
+        int pos = (int)Math.floor(array.size());
+        while (pos >= 0) {
+            siftDown(pos);
+            pos--;
+        }
+        // using a siftDown() algo for creating a new heap is worst case O(n)
+        // using a siftUp() algo would be worst case O(nlogn)
+    }
+
+    public T getMax() {
+        return array.get(0);
+    }
+
+    public T deleteMax() {
+        T toReturn = array.get(0);
+        array.set(0, array.get(array.size() - 1));
+        array.set(array.size() - 1, null);
+        siftDown(0);
+        return toReturn;
+    }
+
+    public void add(T value) {
+        array.add(value);
+        siftUp(array.size() - 1);
+    }
+
+    private void siftUp(int index) {
+        while (index > 0) {
+            int parentIndex = getParentIndex(index);
+            if (array.get(index).compareTo(array.get(parentIndex)) > 0) {
+                swap(index, parentIndex);
+                index = parentIndex;
+            } else {
+                return;
+            }
+        }
+    }
+
+    private void siftDown(int index) {
+        while (index * 2 <= array.size() - 1) {
+            int childIndex = index * 2;
+            if (childIndex + 1 <= array.size() - 1 && array.get(childIndex).compareTo(array.get(childIndex + 1)) < 0) {
+                childIndex++;
+            }
+            if (array.get(index).compareTo(array.get(childIndex)) < 0) {
+                swap(index, childIndex);
+                index = childIndex;
+            } else {
+                return;
+            }
+        }
+    }
+
+    private void swap(int index1, int index2) {
+        T temp = array.get(index1);
+        array.set(index1, array.get(index2));
+        array.set(index2, temp);
+    }
+
+    public static int getLeftChildIndex(int index) {
+        return 2 * index;
+    }
+
+    public static int getRightChildIndex(int index) {
+        return (2 * index) + 1;
+    }
+
+    public static int getParentIndex(int index) {
+        return (int)Math.floor(index / 2);
+    }
+
+    public String toString() {
+        String out = "[";
+        for (T elem : array) {
+            out += elem.toString() + ", ";
+        }
+        out += "]\n";
+        return out;
+    }
+
+    public static void main(String[] args) {
+        ArrayList<Integer> startArr = new ArrayList<>();
+        for (Integer i : new Integer[] {44, 59, 63, 10, 85, 72, 67, 12}) {
+            startArr.add(i);
+        }
+        Heap<Integer> heap = new Heap<>(startArr);
+        System.out.println(heap);
+        heap.add(73);
+        System.out.println(heap);
+    }
+}