summaryrefslogtreecommitdiff
path: root/Year_2/Algorithms
diff options
context:
space:
mode:
authorSanto Cariotti <santo@dcariotti.me>2021-02-06 19:56:36 +0100
committerSanto Cariotti <santo@dcariotti.me>2021-02-06 19:56:36 +0100
commitd2edbc38cac8da52f58c5cd3da6c0c625fa05736 (patch)
treea51e9a4e56fc9d4c7c9e37576dceedca3a0c72b4 /Year_2/Algorithms
parent98f34040820dc3a964b7be59a698323e8cc6c8a3 (diff)
conf: rename
Diffstat (limited to 'Year_2/Algorithms')
-rw-r--r--Year_2/Algorithms/data_structures/heap.c95
-rw-r--r--Year_2/Algorithms/data_structures/heap.rs115
2 files changed, 210 insertions, 0 deletions
diff --git a/Year_2/Algorithms/data_structures/heap.c b/Year_2/Algorithms/data_structures/heap.c
new file mode 100644
index 0000000..be7024b
--- /dev/null
+++ b/Year_2/Algorithms/data_structures/heap.c
@@ -0,0 +1,95 @@
+#include<stdio.h>
+#include<stdlib.h>
+#define HEAP_TYPE 0 // if 0 is max heap, else min heap
+
+unsigned heapsize = 0;
+
+int compare(int x, int y) {
+ return (!HEAP_TYPE) ? x < y : x > y;
+}
+
+void swap(int* a, int x, int y) {
+ int temp = a[x];
+ a[x] = a[y];
+ a[y] = temp;
+}
+
+void insert(int* a, int k) {
+ a[++heapsize] = k;
+ unsigned i = heapsize;
+
+ while(i > 1 && compare(a[i>>1], a[i])) {
+ swap(a, i, i >> 1);
+ i >>= 1;
+ }
+}
+
+void heapify(int* a, int n, int i) {
+ int l = i << 1;
+ int r = l | 1;
+
+ int max = i;
+ if(l <= n && !compare(a[l], a[max])) max = l;
+ if(r <= n && !compare(a[r], a[max])) max = r;
+
+ if(max != i) {
+ swap(a, i, max);
+ heapify(a, n, max);
+ }
+}
+
+void build(int* a, int n) {
+ for(unsigned i = n/2; i > 0; --i) {
+ heapify(a, n, i);
+ }
+}
+
+int extract(int* a) {
+ swap(a, 1, heapsize);
+ --heapsize;
+ heapify(a, heapsize, 1);
+ return *(a+heapsize+1);
+}
+
+int* heapsort(int* a, int n) {
+ int* b = malloc(sizeof(int) * n);
+ build(a, n);
+ for(unsigned i = n-1; i != -1; --i) {
+ b[i] = extract(a);
+ }
+
+ return b;
+}
+
+void increase_key(int* a, int i, int k) {
+ swap(a, i, k);
+ while(i > 1 && compare(a[i>>1], a[i])) {
+ swap(a, i, i >> 1);
+ i >>= 1;
+ }
+}
+
+int main() {
+ heapsize = 0;
+ int* a = malloc(sizeof(int) * 7);
+
+ insert(a, 5);
+ insert(a, 24);
+ insert(a, 1);
+ insert(a, 12);
+ insert(a, 35);
+ insert(a, -1);
+
+ printf("heap = ");
+ for(unsigned i = 1; i <= heapsize; ++i)
+ printf("%d ", *(a+i));
+
+ int n = heapsize;
+ int* b = heapsort(a, heapsize);
+ printf("\nheapsort = ");
+ for(unsigned i = 0; i < n; ++i)
+ printf("%d ", *(b+i));
+ free(b);
+ free(a);
+ return 0;
+}
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);
+}