[usth/ICT2.2] Object Oriented Programming

1 files changed, 61 insertions, 0 deletions

diff --git a/usth/ICT2.2/midterm/src/Heap.java b/usth/ICT2.2/midterm/src/Heap.java
new file mode 100644
index 0000000..3803924
--- /dev/null
+++ b/usth/ICT2.2/midterm/src/Heap.java
@@ -0,0 +1,61 @@
+import java.util.List;
+import java.util.Comparator;
+
+import static java.util.Collections.swap;
+
+public class Heap<T>
+{
+  private List<T> list;
+  private Comparator<T> cmp;
+  private int size;
+
+  public int getSize()
+  {
+    return size;
+  }
+
+  public int getLength()
+  {
+    return list.size();
+  }
+
+  public T get(int i)
+  {
+    return list.get(i);
+  }
+
+  public void heapify(int i)
+  {
+    int right = i + 1 << 1;
+    int left = right - 1;
+    int largest = i;
+
+    if (left < size && cmp.compare(get(left), get(largest)) > 0)
+      largest = left;
+    if (right < size && cmp.compare(get(right), get(largest)) > 0)
+      largest = right;
+    if (largest != i)
+      {
+        swap(list, i, largest);
+        heapify(largest);
+      }
+  }
+
+  public Heap(List<T> a, Comparator<T> c)
+  {
+    list = a;
+    size = a.size();
+    cmp = c;
+    for (int i = size >> 1; i-- > 0;)
+      heapify(i);
+  }
+
+  public T pop() throws RuntimeException
+  {
+    if (size < 1)
+      throw new RuntimeException("heap underflow");
+    swap(list, 0, --size);
+    heapify(0);
+    return get(size);
+  }
+}