added heap data structureHEADmaster

2 files changed, 159 insertions, 36 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);
+    }
+}
diff --git a/SelfBalancingBinarySearchTree.java b/SelfBalancingBinarySearchTree.java
index efb6ab2..31a5343 100644
--- a/SelfBalancingBinarySearchTree.java
+++ b/SelfBalancingBinarySearchTree.java
@@ -95,6 +95,12 @@ public class SelfBalancingBinarySearchTree<T extends Comparable<T>> {
             }
             return leftHeight - rightHeight;
         }
+
+        public void leftRotate() {
+            BinaryTreeNode<T> newRoot = getRightChild();
+            newRoot.leftChild = this;
+            this.rightChild = newRoot.getLeftChild();
+        }
     }
 
     public static class DuplicateItemException extends Exception {
@@ -380,47 +386,62 @@ public class SelfBalancingBinarySearchTree<T extends Comparable<T>> {
     
     public static void main(String[] args) {
         SelfBalancingBinarySearchTree<Integer> bst = new SelfBalancingBinarySearchTree<>();
+        // try {
+        //     bst.recursiveAdd(25);
+        //     bst.recursiveAdd(15);
+        //     bst.recursiveAdd(50);
+        //     bst.recursiveAdd(10);
+        //     bst.recursiveAdd(22);
+        //     bst.iterativeAdd(35);
+        //     bst.iterativeAdd(70);
+        //     bst.iterativeAdd(4);
+        //     bst.iterativeAdd(12);
+        //     bst.iterativeAdd(18);
+        //     bst.iterativeAdd(24);
+        //     bst.iterativeAdd(31);
+        //     bst.iterativeAdd(44);
+        //     bst.iterativeAdd(66);
+        //     bst.iterativeAdd(90);
+        // } catch (DuplicateItemException e) {
+        //     e.printStackTrace();
+        // }
+
+        // System.out.println("In-Order Traversal:");
+        // for (Integer s : bst.new InOrderIterator()) {
+        //     System.out.print(s + ", ");
+        // }
+        // System.out.println("");
+        // System.out.println("\nPre-Order Traversal:");
+        // for (Integer s : bst.new PreOrderIterator()) {
+        //     System.out.print(s + ", ");
+        // }
+        // System.out.println("");
+        // System.out.println("\nPost-Order Traversal:");
+        // for (Integer s : bst.new PostOrderIterator()) {
+        //     System.out.print(s + ", ");
+        // }
+        // System.out.println("");
+        // System.out.println("\nBreadth first Traversal:");
+        // for (Integer s : bst.new BreadthFirstIterator()) {
+        //     System.out.print(s + ", ");
+        // }
+        // System.out.println("\n");
         try {
-            bst.recursiveAdd(25);
-            bst.recursiveAdd(15);
-            bst.recursiveAdd(50);
-            bst.recursiveAdd(10);
-            bst.recursiveAdd(22);
-            bst.iterativeAdd(35);
-            bst.iterativeAdd(70);
-            bst.iterativeAdd(4);
-            bst.iterativeAdd(12);
-            bst.iterativeAdd(18);
-            bst.iterativeAdd(24);
-            bst.iterativeAdd(31);
-            bst.iterativeAdd(44);
-            bst.iterativeAdd(66);
-            bst.iterativeAdd(90);
+            bst.recursiveAdd(9);
+            bst.recursiveAdd(6);
+            bst.recursiveAdd(20);
+            bst.recursiveAdd(4);
+            bst.recursiveAdd(7);
+            bst.iterativeAdd(15);
+            bst.iterativeAdd(26);
+            bst.iterativeAdd(22);
+            bst.iterativeAdd(30);
         } catch (DuplicateItemException e) {
             e.printStackTrace();
         }
 
-        System.out.println("In-Order Traversal:");
-        for (Integer s : bst.new InOrderIterator()) {
-            System.out.print(s + ", ");
-        }
-        System.out.println("");
-        System.out.println("\nPre-Order Traversal:");
-        for (Integer s : bst.new PreOrderIterator()) {
-            System.out.print(s + ", ");
-        }
-        System.out.println("");
-        System.out.println("\nPost-Order Traversal:");
-        for (Integer s : bst.new PostOrderIterator()) {
-            System.out.print(s + ", ");
-        }
-        System.out.println("");
-        System.out.println("\nBreadth first Traversal:");
-        for (Integer s : bst.new BreadthFirstIterator()) {
-            System.out.print(s + ", ");
-        }
-        System.out.println("\n");
-
+        System.out.println(bst);
+        bst.root.leftRotate();
         System.out.println(bst);
     }
 }
\ No newline at end of file