From d2edbc38cac8da52f58c5cd3da6c0c625fa05736 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sat, 6 Feb 2021 19:56:36 +0100 Subject: conf: rename --- Year_2/Algorithms/data_structures/heap.c | 95 ++++++++++++++++++++++++ Year_2/Algorithms/data_structures/heap.rs | 115 ++++++++++++++++++++++++++++++ 2 files changed, 210 insertions(+) create mode 100644 Year_2/Algorithms/data_structures/heap.c create mode 100644 Year_2/Algorithms/data_structures/heap.rs (limited to 'Year_2/Algorithms/data_structures') 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 +#include +#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 { + array: [T; 32], + is_minheap: bool, + size: usize, +} + +impl Heap +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(array: [T; 32], n: usize) -> Heap { + let mut heap = Heap::::new(); + + heap.size = n; + heap.array = array; + + for i in (1..=n / 2).rev() { + heap.heapify(i); + } + + heap +} + +fn heapsort(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::::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