From d2edbc38cac8da52f58c5cd3da6c0c625fa05736 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sat, 6 Feb 2021 19:56:36 +0100 Subject: conf: rename --- 2_anno/Algoritmi/data_structures/heap.c | 95 ------------------------- 2_anno/Algoritmi/data_structures/heap.rs | 115 ------------------------------- 2 files changed, 210 deletions(-) delete mode 100644 2_anno/Algoritmi/data_structures/heap.c delete mode 100644 2_anno/Algoritmi/data_structures/heap.rs (limited to '2_anno') diff --git a/2_anno/Algoritmi/data_structures/heap.c b/2_anno/Algoritmi/data_structures/heap.c deleted file mode 100644 index be7024b..0000000 --- a/2_anno/Algoritmi/data_structures/heap.c +++ /dev/null @@ -1,95 +0,0 @@ -#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/2_anno/Algoritmi/data_structures/heap.rs b/2_anno/Algoritmi/data_structures/heap.rs deleted file mode 100644 index 9dde55c..0000000 --- a/2_anno/Algoritmi/data_structures/heap.rs +++ /dev/null @@ -1,115 +0,0 @@ -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