From d2edbc38cac8da52f58c5cd3da6c0c625fa05736 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Sat, 6 Feb 2021 19:56:36 +0100
Subject: conf: rename

---
 Year_2/Algorithms/data_structures/heap.rs | 115 ++++++++++++++++++++++++++++++
 1 file changed, 115 insertions(+)
 create mode 100644 Year_2/Algorithms/data_structures/heap.rs

(limited to 'Year_2/Algorithms/data_structures/heap.rs')

diff --git a/Year_2/Algorithms/data_structures/heap.rs b/Year_2/Algorithms/data_structures/heap.rs
new file mode 100644
index 0000000..9dde55c
--- /dev/null
+++ b/Year_2/Algorithms/data_structures/heap.rs
@@ -0,0 +1,115 @@
+struct Heap<T> {
+    array: [T; 32],
+    is_minheap: bool,
+    size: usize,
+}
+
+impl<T> Heap<T>
+where
+    T: PartialOrd + Copy + Default,
+{
+    fn new() -> Self {
+        Heap {
+            array: [T::default(); 32],
+            is_minheap: false,
+            size: 0,
+        }
+    }
+
+    fn insert(&mut self, k: T) {
+        self.size += 1;
+        self.array[self.size] = k;
+        let mut i = self.size;
+
+        while i > 1 && self.compare(i >> 1, i) {
+            let temp = self.array[i];
+            self.array[i] = self.array[i >> 1];
+            self.array[i >> 1] = temp;
+            i >>= 1;
+        }
+    }
+
+    fn heapify(&mut self, i: usize) {
+        let l = i << 1;
+        let r = l | 1;
+
+        let mut max = i;
+        if l <= self.size && !self.compare(l, max) {
+            max = l;
+        }
+        if r <= self.size && !self.compare(r, max) {
+            max = r;
+        }
+
+        if max != i {
+            let temp = self.array[i];
+            self.array[i] = self.array[max];
+            self.array[max] = temp;
+            self.heapify(max);
+        }
+    }
+
+    fn extract(&mut self) -> T {
+        let temp = self.array[1];
+        self.array[1] = self.array[self.size];
+        self.array[self.size] = temp;
+        self.size -= 1;
+
+        self.heapify(1);
+
+        self.array[self.size + 1]
+    }
+
+    fn compare(&self, x: usize, y: usize) -> bool {
+        match self.is_minheap {
+            false => self.array[x] < self.array[y],
+            true => self.array[x] > self.array[y],
+        }
+    }
+}
+
+fn build<T: PartialOrd + Copy + Default>(array: [T; 32], n: usize) -> Heap<T> {
+    let mut heap = Heap::<T>::new();
+
+    heap.size = n;
+    heap.array = array;
+
+    for i in (1..=n / 2).rev() {
+        heap.heapify(i);
+    }
+
+    heap
+}
+
+fn heapsort<T: PartialOrd + Copy + Default>(array: [T; 32], n: usize) -> [T; 32] {
+    let mut heap = build(array, n);
+    let mut arr: [T; 32] = [T::default(); 32];
+    for i in (0..n).rev() {
+        arr[i] = heap.extract();
+    }
+
+    arr
+}
+
+fn main() {
+    let mut h = Heap::<i32>::new();
+    println!("{:?}", h.array);
+    h.insert(5);
+    h.insert(24);
+    h.insert(1);
+    h.insert(12);
+    h.insert(35);
+    h.insert(-1);
+    println!("{:?}\n", h.array);
+
+    let mut arr: [i32; 32] = [0; 32];
+    arr[1] = 5;
+    arr[2] = 24;
+    arr[3] = 1;
+    arr[4] = 12;
+    arr[5] = 35;
+    arr[6] = -1;
+    println!("{:?}", &arr);
+    let hh = heapsort(arr, 6);
+    println!("{:?}", hh);
+}
-- 
cgit v1.2.3-18-g5258