From c37e08f643475a1a3fb3e2e3f5d4cf81297970d7 Mon Sep 17 00:00:00 2001
From: jwansek <eddie.atten.ea29@gmail.com>
Date: Mon, 17 May 2021 23:23:14 +0100
Subject: added heap data structure
---
Heap.java | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 102 insertions(+)
create mode 100644 Heap.java
(limited to 'Heap.java')
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);
+ }
+}
--
cgit v1.2.3