1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
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);
}
|
