diff options
author | Santo Cariotti <dcariotti24@gmail.com> | 2020-10-23 22:07:39 +0200 |
---|---|---|
committer | Santo Cariotti <dcariotti24@gmail.com> | 2020-10-23 22:07:39 +0200 |
commit | 98f34040820dc3a964b7be59a698323e8cc6c8a3 (patch) | |
tree | e7ae459fd29dd26a70d6df567294e73fd44a0501 /2_anno | |
parent | 27f23d04f5997c4ce0f90f39e0d29285fbf5c565 (diff) |
feat: variant of heapsort in rust
Diffstat (limited to '2_anno')
-rw-r--r-- | 2_anno/Algoritmi/data_structures/heap.rs | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/2_anno/Algoritmi/data_structures/heap.rs b/2_anno/Algoritmi/data_structures/heap.rs new file mode 100644 index 0000000..9dde55c --- /dev/null +++ b/2_anno/Algoritmi/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); +} |