sorting_race/services/sorters/
heap.rs

1//! Heap Sort implementation
2
3use crate::models::traits::{Sorter, StepResult, Telemetry, Markers};
4use std::any::Any;
5
6#[derive(Debug, Clone, PartialEq)]
7enum HeapSortState {
8    BuildHeap,
9    ExtractMax,
10}
11
12/// Heap Sort algorithm implementation
13#[derive(Debug)]
14pub struct HeapSort {
15    data: Vec<i32>,
16    heap_size: usize,
17    current_index: usize,
18    state: HeapSortState,
19    comparisons: u64,
20    moves: u64,
21    complete: bool,
22}
23
24impl HeapSort {
25    /// Create a new HeapSort instance
26    pub fn new() -> Self {
27        Self {
28            data: Vec::new(),
29            heap_size: 0,
30            current_index: 0,
31            state: HeapSortState::BuildHeap,
32            comparisons: 0,
33            moves: 0,
34            complete: false,
35        }
36    }
37
38    fn heapify(&mut self, mut root: usize, budget: &mut usize) -> bool {
39        // Check if we have enough budget for worst case (2 * log(n) comparisons)
40        let estimated_comparisons = ((self.heap_size as f32).log2().ceil() * 2.0) as usize;
41        if *budget < estimated_comparisons {
42            return false; // Not enough budget to complete heapify
43        }
44        
45        loop {
46            let mut largest = root;
47            let left = 2 * root + 1;
48            let right = 2 * root + 2;
49
50            // Compare with left child
51            if left < self.heap_size {
52                *budget = budget.saturating_sub(1);
53                self.comparisons += 1;
54                if self.data[left] > self.data[largest] {
55                    largest = left;
56                }
57            }
58
59            // Compare with right child  
60            if right < self.heap_size {
61                *budget = budget.saturating_sub(1);
62                self.comparisons += 1;
63                if self.data[right] > self.data[largest] {
64                    largest = right;
65                }
66            }
67
68            // If largest is not root, swap and continue
69            if largest != root {
70                self.data.swap(root, largest);
71                self.moves += 1;
72                root = largest; // Continue with the child
73            } else {
74                break; // Heap property satisfied
75            }
76        }
77
78        true // Heapify complete
79    }
80}
81
82impl Default for HeapSort {
83    fn default() -> Self {
84        Self::new()
85    }
86}
87
88impl Sorter for HeapSort {
89    fn step(&mut self, budget: usize) -> StepResult {
90        if self.complete || self.data.len() <= 1 {
91            return StepResult {
92                comparisons_used: 0,
93                moves_made: 0,
94                continued: false,
95            };
96        }
97
98        let initial_comparisons = self.comparisons;
99        let initial_moves = self.moves;
100        let mut remaining_budget = budget;
101
102        match self.state {
103            HeapSortState::BuildHeap => {
104                while remaining_budget > 0 && self.current_index > 0 {
105                    let finished = self.heapify(self.current_index - 1, &mut remaining_budget);
106                    
107                    if finished {
108                        if self.current_index == 1 {
109                            // Heap building complete, start extraction
110                            self.state = HeapSortState::ExtractMax;
111                            self.current_index = self.data.len();
112                            break;
113                        } else {
114                            self.current_index -= 1;
115                        }
116                    } else {
117                        break; // Need more budget
118                    }
119                }
120            }
121            HeapSortState::ExtractMax => {
122                while remaining_budget > 0 && self.heap_size > 1 {
123                    // Move current maximum to the end
124                    self.data.swap(0, self.heap_size - 1);
125                    self.moves += 1;
126                    self.heap_size -= 1;
127                    
128                    // Heapify the reduced heap
129                    let finished = self.heapify(0, &mut remaining_budget);
130                    
131                    if !finished {
132                        // Restore heap_size since we couldn't complete the heapify
133                        self.heap_size += 1;
134                        self.data.swap(0, self.heap_size - 1);
135                        self.moves += 1;
136                        break; // Need more budget
137                    }
138                    
139                    if self.heap_size <= 1 {
140                        self.complete = true;
141                        break;
142                    }
143                }
144            }
145        }
146
147        StepResult {
148            comparisons_used: (self.comparisons - initial_comparisons) as usize,
149            moves_made: (self.moves - initial_moves) as usize,
150            continued: !self.complete,
151        }
152    }
153
154    fn is_complete(&self) -> bool {
155        self.complete
156    }
157
158    fn get_telemetry(&self) -> Telemetry {
159        let mut markers = Markers::default();
160        
161        // Show heap boundary
162        if !self.complete {
163            markers.heap_boundary = Some(self.heap_size);
164            
165            match self.state {
166                HeapSortState::BuildHeap => {
167                    if self.current_index > 0 {
168                        markers.cursors = vec![self.current_index - 1];
169                    }
170                }
171                HeapSortState::ExtractMax => {
172                    if self.heap_size > 0 {
173                        markers.cursors = vec![0]; // Root of heap
174                        if self.heap_size < self.data.len() {
175                            markers.cursors.push(self.heap_size - 1);
176                        }
177                    }
178                }
179            }
180        }
181
182        Telemetry {
183            total_comparisons: self.comparisons,
184            total_moves: self.moves,
185            memory_current: self.get_memory_usage(),
186            memory_peak: self.get_memory_usage(),
187            highlights: markers.cursors.clone(),
188            markers,
189            status_text: if self.complete {
190                "Completed".to_string()
191            } else {
192                match self.state {
193                    HeapSortState::BuildHeap => {
194                        format!("Building heap, processing index {}", 
195                               if self.current_index > 0 { self.current_index - 1 } else { 0 })
196                    }
197                    HeapSortState::ExtractMax => {
198                        format!("Extracting max, heap size {}", self.heap_size)
199                    }
200                }
201            },
202            progress_hint: if self.complete {
203                1.0
204            } else if self.data.len() <= 1 {
205                1.0
206            } else {
207                match self.state {
208                    HeapSortState::BuildHeap => {
209                        let total_build_steps = (self.data.len() / 2).max(1) as f32;
210                        let completed_steps = (self.data.len() / 2) as f32 - self.current_index as f32;
211                        let progress = (completed_steps / total_build_steps).max(0.0).min(0.5);
212                        if progress.is_finite() { progress } else { 0.0 }
213                    }
214                    HeapSortState::ExtractMax => {
215                        if self.data.is_empty() {
216                            1.0
217                        } else {
218                            let extraction_progress = (self.data.len() - self.heap_size) as f32 / self.data.len() as f32;
219                            let progress = 0.5 + extraction_progress * 0.5;
220                            if progress.is_finite() { progress.min(1.0).max(0.0) } else { 0.5 }
221                        }
222                    }
223                }
224            },
225        }
226    }
227
228    fn reset(&mut self, data: Vec<i32>) {
229        self.data = data;
230        self.heap_size = self.data.len();
231        self.current_index = self.data.len() / 2; // Start from last non-leaf node
232        self.state = HeapSortState::BuildHeap;
233        self.comparisons = 0;
234        self.moves = 0;
235        self.complete = self.data.len() <= 1;
236    }
237
238    fn name(&self) -> &str {
239        "Heap Sort"
240    }
241
242    fn get_array(&self) -> &[i32] {
243        &self.data
244    }
245
246    fn get_memory_usage(&self) -> usize {
247        // Report size of the data array in bytes
248        self.data.len() * std::mem::size_of::<i32>()
249    }
250
251    fn as_any(&self) -> &dyn Any {
252        self
253    }
254
255    fn as_any_mut(&mut self) -> &mut dyn Any {
256        self
257    }
258}
sorting_race/services/sorters/heap.rs

sorting_race/services/sorters/
heap.rs
