Struct algorithms_rs::heap::Heap

source · 
pub struct Heap<T> { /* private fields */ }
Expand description

Heap

Implementations§

Creating a empty heap

use algorithms_rs::Heap;

let empty_heap = Heap::<i32>::new();

assert_eq!(empty_heap.is_empty(), true);
Examples found in repository?
src/heap.rs (line 27)
26
27
28

    fn default() -> Self {
        Self::new()
    }

Creating a heap from an array

use algorithms_rs::Heap;

let empty_heap = Heap::<i32>::from_vector(&vec![1]).unwrap();

assert_eq!(empty_heap.is_empty(), true);

Length of the heap

Examples found in repository?
src/heap.rs (line 75)
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Get the internal data of the heap
    pub fn inner_vec(&self) -> &[T] {
        &self.data
    }

    /// Big root heap adjustment Recursive algorithm implementation
    pub fn max_heapify(&mut self, index: usize) {
        // setting largest is index
        let mut largest = index;
        let left = left(index);
        let right = right(index);

        // if left > largest then larget = left
        if left <= self.len() && self.data.get(largest) < self.data.get(left) {
            largest = left;
        }

        // if right > largest then largest = right
        if right <= self.len() && self.data.get(largest) < self.data.get(right) {
            largest = right;
        }

        if largest != index {
            // swap vector index , largest value
            self.data.swap(index, largest);
            // rec call max_heapify
            self.max_heapify(largest);
        }
    }

    /// Small root heap adjustment Recursive algorithm implementation
    pub fn min_heapify(&mut self, index: usize) {
        // setting min is index
        let mut min = index;
        let left = left(index);
        let right = right(index);

        // if min > left then min = left
        if left <= self.len() && self.data.get(min) > self.data.get(left) {
            min = left;
        }

        // if min > right then min = right
        if right <= self.len() && self.data.get(min) > self.data.get(right) {
            min = right;
        }

        if min != index {
            // swap vector index, min value
            self.data.swap(index, min);
            // rec call min_heapify
            self.min_heapify(min);
        }
    }

    /// Small root heap upward adjustment Non-recursive algorithm implementation
    pub fn min_sift_up(&mut self, index: usize) {
        let mut cur_idx = index;
        loop {
            // if cur_idx is root idx will break
            if cur_idx == 0 {
                break;
            }

            // get parent index
            let parent_idx = parent(cur_idx);

            // when parent node <= child node will break
            if self.data[parent_idx] <= self.data[cur_idx] {
                break;
            }

            // swap parent node idx with child node idx
            self.data.swap(parent_idx, cur_idx);

            // now cur_idx is assign to it's parent idx
            cur_idx = parent_idx;
        }
    }

    /// Big root heap upward adjustment Non-recursive algorithm implementation
    pub fn max_sift_up(&mut self, index: usize) {
        let mut cur_idx = index;
        loop {
            // if cur_idx is root idx will break
            if cur_idx == 0 {
                break;
            }

            // get parent index
            let parent_idx = parent(cur_idx);

            // when child node <= parent node will break
            if self.data[cur_idx] <= self.data[parent_idx] {
                break;
            }

            // swap parent node idx with child node idx
            self.data.swap(parent_idx, cur_idx);

            // now cur_idx is assign to it's parent idx
            cur_idx = parent_idx;
        }
    }

    /// Small root heap downward adjustment Non-recursive algorithm implementation
    pub fn min_sift_down(&mut self, heap_len: usize) {
        let mut cur_idx = 0usize;
        loop {
            // get cur_idx has left child idx
            let mut child_idx = 2 * cur_idx + 1;

            if cur_idx > heap_len || child_idx > heap_len {
                break;
            }

            // child is the left child of cur_idx
            // find left child and right child lesser child
            if child_idx + 1 < heap_len && self.data[child_idx + 1] < self.data[child_idx] {
                // right_child_idx is the right child of cur_idx
                child_idx += 1;
            }

            // child is the lesser child of cur_idx
            // if child's parent (cur_idx) <= child will break
            if self.data[cur_idx] <= self.data[child_idx] {
                break;
            }

            // otherwise swap lesser child idx with cur_idx(parent idx)
            self.data.swap(child_idx, cur_idx);

            // assign cur_idx with lesser child idx
            cur_idx = child_idx;
        }
    }

    /// Big root heap downward adjustment Non-recursive algorithm implementation
    pub fn max_sift_down(&mut self, heap_len: usize) {
        let mut cur_idx = 0usize;
        loop {
            // get cur_idx has left child idx
            let mut child_idx = 2 * cur_idx + 1;

            if cur_idx > heap_len || child_idx > heap_len {
                break;
            }

            // child is the left child of cur_idx
            // find left child and right child bigger child
            if child_idx + 1 < heap_len && self.data[child_idx + 1] > self.data[child_idx] {
                child_idx += 1;
            }

            // child is the lesser child of cur_idx
            // if child's parent (cur_idx) > child will break
            if self.data[cur_idx] > self.data[child_idx] {
                break;
            }

            // otherwise swap lesser child idx with cur_idx(parent idx)
            self.data.swap(child_idx, cur_idx);

            // assign cur_idx with lesser child idx
            cur_idx = child_idx;
        }
    }

    /// Constructing a big root heap by recursive adjustment algorithm of big root heap
    pub fn build_max_heap_by_max_heapify(&mut self) {
        for index in (0..(self.len() / 2)).rev() {
            self.max_heapify(index);
        }
    }

    /// Construction of large root heap by non-recursive adjustment algorithm of large root heap
    ///
    /// ```rust
    /// use algorithms_rs::Heap;
    ///
    /// let mut max_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();
    ///
    /// max_heap.build_max_heap_by_shift_up();
    ///
    /// assert_eq!(max_heap.inner_vec().to_vec(), vec![5, 4, 2, 3, 1])
    /// ```
    pub fn build_max_heap_by_shift_up(&mut self) {
        // for i = [2; n]
        // invariant : heap(1, i - 1)
        // max_sift_up(i)
        // heap(1, i)
        for index in (0..self.data.len()).rev() {
            self.max_sift_up(index);
        }
    }

    /// Constructing rootlet heap by recursive adjustment algorithm of rootlet heap
    pub fn build_min_heap_by_min_heapify(&mut self) {
        for index in (0..(self.len() / 2)).rev() {
            self.min_heapify(index);
        }
    }

Determine if the heap is empty

Get the internal data of the heap

Big root heap adjustment Recursive algorithm implementation

Examples found in repository?
src/heap.rs (line 104)
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323

    pub fn max_heapify(&mut self, index: usize) {
        // setting largest is index
        let mut largest = index;
        let left = left(index);
        let right = right(index);

        // if left > largest then larget = left
        if left <= self.len() && self.data.get(largest) < self.data.get(left) {
            largest = left;
        }

        // if right > largest then largest = right
        if right <= self.len() && self.data.get(largest) < self.data.get(right) {
            largest = right;
        }

        if largest != index {
            // swap vector index , largest value
            self.data.swap(index, largest);
            // rec call max_heapify
            self.max_heapify(largest);
        }
    }

    /// Small root heap adjustment Recursive algorithm implementation
    pub fn min_heapify(&mut self, index: usize) {
        // setting min is index
        let mut min = index;
        let left = left(index);
        let right = right(index);

        // if min > left then min = left
        if left <= self.len() && self.data.get(min) > self.data.get(left) {
            min = left;
        }

        // if min > right then min = right
        if right <= self.len() && self.data.get(min) > self.data.get(right) {
            min = right;
        }

        if min != index {
            // swap vector index, min value
            self.data.swap(index, min);
            // rec call min_heapify
            self.min_heapify(min);
        }
    }

    /// Small root heap upward adjustment Non-recursive algorithm implementation
    pub fn min_sift_up(&mut self, index: usize) {
        let mut cur_idx = index;
        loop {
            // if cur_idx is root idx will break
            if cur_idx == 0 {
                break;
            }

            // get parent index
            let parent_idx = parent(cur_idx);

            // when parent node <= child node will break
            if self.data[parent_idx] <= self.data[cur_idx] {
                break;
            }

            // swap parent node idx with child node idx
            self.data.swap(parent_idx, cur_idx);

            // now cur_idx is assign to it's parent idx
            cur_idx = parent_idx;
        }
    }

    /// Big root heap upward adjustment Non-recursive algorithm implementation
    pub fn max_sift_up(&mut self, index: usize) {
        let mut cur_idx = index;
        loop {
            // if cur_idx is root idx will break
            if cur_idx == 0 {
                break;
            }

            // get parent index
            let parent_idx = parent(cur_idx);

            // when child node <= parent node will break
            if self.data[cur_idx] <= self.data[parent_idx] {
                break;
            }

            // swap parent node idx with child node idx
            self.data.swap(parent_idx, cur_idx);

            // now cur_idx is assign to it's parent idx
            cur_idx = parent_idx;
        }
    }

    /// Small root heap downward adjustment Non-recursive algorithm implementation
    pub fn min_sift_down(&mut self, heap_len: usize) {
        let mut cur_idx = 0usize;
        loop {
            // get cur_idx has left child idx
            let mut child_idx = 2 * cur_idx + 1;

            if cur_idx > heap_len || child_idx > heap_len {
                break;
            }

            // child is the left child of cur_idx
            // find left child and right child lesser child
            if child_idx + 1 < heap_len && self.data[child_idx + 1] < self.data[child_idx] {
                // right_child_idx is the right child of cur_idx
                child_idx += 1;
            }

            // child is the lesser child of cur_idx
            // if child's parent (cur_idx) <= child will break
            if self.data[cur_idx] <= self.data[child_idx] {
                break;
            }

            // otherwise swap lesser child idx with cur_idx(parent idx)
            self.data.swap(child_idx, cur_idx);

            // assign cur_idx with lesser child idx
            cur_idx = child_idx;
        }
    }

    /// Big root heap downward adjustment Non-recursive algorithm implementation
    pub fn max_sift_down(&mut self, heap_len: usize) {
        let mut cur_idx = 0usize;
        loop {
            // get cur_idx has left child idx
            let mut child_idx = 2 * cur_idx + 1;

            if cur_idx > heap_len || child_idx > heap_len {
                break;
            }

            // child is the left child of cur_idx
            // find left child and right child bigger child
            if child_idx + 1 < heap_len && self.data[child_idx + 1] > self.data[child_idx] {
                child_idx += 1;
            }

            // child is the lesser child of cur_idx
            // if child's parent (cur_idx) > child will break
            if self.data[cur_idx] > self.data[child_idx] {
                break;
            }

            // otherwise swap lesser child idx with cur_idx(parent idx)
            self.data.swap(child_idx, cur_idx);

            // assign cur_idx with lesser child idx
            cur_idx = child_idx;
        }
    }

    /// Constructing a big root heap by recursive adjustment algorithm of big root heap
    pub fn build_max_heap_by_max_heapify(&mut self) {
        for index in (0..(self.len() / 2)).rev() {
            self.max_heapify(index);
        }
    }

    /// Construction of large root heap by non-recursive adjustment algorithm of large root heap
    ///
    /// ```rust
    /// use algorithms_rs::Heap;
    ///
    /// let mut max_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();
    ///
    /// max_heap.build_max_heap_by_shift_up();
    ///
    /// assert_eq!(max_heap.inner_vec().to_vec(), vec![5, 4, 2, 3, 1])
    /// ```
    pub fn build_max_heap_by_shift_up(&mut self) {
        // for i = [2; n]
        // invariant : heap(1, i - 1)
        // max_sift_up(i)
        // heap(1, i)
        for index in (0..self.data.len()).rev() {
            self.max_sift_up(index);
        }
    }

    /// Constructing rootlet heap by recursive adjustment algorithm of rootlet heap
    pub fn build_min_heap_by_min_heapify(&mut self) {
        for index in (0..(self.len() / 2)).rev() {
            self.min_heapify(index);
        }
    }

    /// Construction of rootlet heap by non-recursive adjustment algorithm of rootlet heap
    ///
    /// ```rust
    ///  use algorithms_rs::Heap;
    ///
    ///  let mut min_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();
    ///
    ///  min_heap.build_min_heap_by_siftup();
    ///
    ///  assert_eq!(min_heap.inner_vec().to_vec(), vec![1, 2, 3, 4, 5]);
    /// ```
    pub fn build_min_heap_by_siftup(&mut self) {
        // for i = [2; n]
        // invariant : heap(1, i - 1)
        // min_sift_up(i)
        // heap(1, i)
        for index in 0..self.data.len() {
            self.min_sift_up(index);
        }
    }

    /// Ascending sort implementation based on recursive implementation of the big root heap
    ///
    /// ```rust
    /// use algorithms_rs::Heap;
    ///
    /// let mut max_heap = Heap::from_vector(&vec![5, 3, 7, 9, 10, 23, 45, 23, 12, 23, 0, 12, 32]).unwrap();
    ///
    /// max_heap.heap_sort_by_max_heap();
    ///
    /// assert_eq!(
    ///    max_heap.inner_vec().to_vec(),
    ///    vec![0, 3, 5, 7, 9, 10, 12, 12, 23, 23, 23, 32, 45]
    /// );
    /// ```
    pub fn heap_sort_by_max_heap(&mut self) {
        self.build_max_heap_by_max_heapify();
        for index in (1..self.data.len()).rev() {
            self.data.swap(0, index);
            self.size -= 1;
            self.max_heapify(0);
        }
    }

Small root heap adjustment Recursive algorithm implementation

Examples found in repository?
src/heap.rs (line 129)
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343

    pub fn min_heapify(&mut self, index: usize) {
        // setting min is index
        let mut min = index;
        let left = left(index);
        let right = right(index);

        // if min > left then min = left
        if left <= self.len() && self.data.get(min) > self.data.get(left) {
            min = left;
        }

        // if min > right then min = right
        if right <= self.len() && self.data.get(min) > self.data.get(right) {
            min = right;
        }

        if min != index {
            // swap vector index, min value
            self.data.swap(index, min);
            // rec call min_heapify
            self.min_heapify(min);
        }
    }

    /// Small root heap upward adjustment Non-recursive algorithm implementation
    pub fn min_sift_up(&mut self, index: usize) {
        let mut cur_idx = index;
        loop {
            // if cur_idx is root idx will break
            if cur_idx == 0 {
                break;
            }

            // get parent index
            let parent_idx = parent(cur_idx);

            // when parent node <= child node will break
            if self.data[parent_idx] <= self.data[cur_idx] {
                break;
            }

            // swap parent node idx with child node idx
            self.data.swap(parent_idx, cur_idx);

            // now cur_idx is assign to it's parent idx
            cur_idx = parent_idx;
        }
    }

    /// Big root heap upward adjustment Non-recursive algorithm implementation
    pub fn max_sift_up(&mut self, index: usize) {
        let mut cur_idx = index;
        loop {
            // if cur_idx is root idx will break
            if cur_idx == 0 {
                break;
            }

            // get parent index
            let parent_idx = parent(cur_idx);

            // when child node <= parent node will break
            if self.data[cur_idx] <= self.data[parent_idx] {
                break;
            }

            // swap parent node idx with child node idx
            self.data.swap(parent_idx, cur_idx);

            // now cur_idx is assign to it's parent idx
            cur_idx = parent_idx;
        }
    }

    /// Small root heap downward adjustment Non-recursive algorithm implementation
    pub fn min_sift_down(&mut self, heap_len: usize) {
        let mut cur_idx = 0usize;
        loop {
            // get cur_idx has left child idx
            let mut child_idx = 2 * cur_idx + 1;

            if cur_idx > heap_len || child_idx > heap_len {
                break;
            }

            // child is the left child of cur_idx
            // find left child and right child lesser child
            if child_idx + 1 < heap_len && self.data[child_idx + 1] < self.data[child_idx] {
                // right_child_idx is the right child of cur_idx
                child_idx += 1;
            }

            // child is the lesser child of cur_idx
            // if child's parent (cur_idx) <= child will break
            if self.data[cur_idx] <= self.data[child_idx] {
                break;
            }

            // otherwise swap lesser child idx with cur_idx(parent idx)
            self.data.swap(child_idx, cur_idx);

            // assign cur_idx with lesser child idx
            cur_idx = child_idx;
        }
    }

    /// Big root heap downward adjustment Non-recursive algorithm implementation
    pub fn max_sift_down(&mut self, heap_len: usize) {
        let mut cur_idx = 0usize;
        loop {
            // get cur_idx has left child idx
            let mut child_idx = 2 * cur_idx + 1;

            if cur_idx > heap_len || child_idx > heap_len {
                break;
            }

            // child is the left child of cur_idx
            // find left child and right child bigger child
            if child_idx + 1 < heap_len && self.data[child_idx + 1] > self.data[child_idx] {
                child_idx += 1;
            }

            // child is the lesser child of cur_idx
            // if child's parent (cur_idx) > child will break
            if self.data[cur_idx] > self.data[child_idx] {
                break;
            }

            // otherwise swap lesser child idx with cur_idx(parent idx)
            self.data.swap(child_idx, cur_idx);

            // assign cur_idx with lesser child idx
            cur_idx = child_idx;
        }
    }

    /// Constructing a big root heap by recursive adjustment algorithm of big root heap
    pub fn build_max_heap_by_max_heapify(&mut self) {
        for index in (0..(self.len() / 2)).rev() {
            self.max_heapify(index);
        }
    }

    /// Construction of large root heap by non-recursive adjustment algorithm of large root heap
    ///
    /// ```rust
    /// use algorithms_rs::Heap;
    ///
    /// let mut max_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();
    ///
    /// max_heap.build_max_heap_by_shift_up();
    ///
    /// assert_eq!(max_heap.inner_vec().to_vec(), vec![5, 4, 2, 3, 1])
    /// ```
    pub fn build_max_heap_by_shift_up(&mut self) {
        // for i = [2; n]
        // invariant : heap(1, i - 1)
        // max_sift_up(i)
        // heap(1, i)
        for index in (0..self.data.len()).rev() {
            self.max_sift_up(index);
        }
    }

    /// Constructing rootlet heap by recursive adjustment algorithm of rootlet heap
    pub fn build_min_heap_by_min_heapify(&mut self) {
        for index in (0..(self.len() / 2)).rev() {
            self.min_heapify(index);
        }
    }

    /// Construction of rootlet heap by non-recursive adjustment algorithm of rootlet heap
    ///
    /// ```rust
    ///  use algorithms_rs::Heap;
    ///
    ///  let mut min_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();
    ///
    ///  min_heap.build_min_heap_by_siftup();
    ///
    ///  assert_eq!(min_heap.inner_vec().to_vec(), vec![1, 2, 3, 4, 5]);
    /// ```
    pub fn build_min_heap_by_siftup(&mut self) {
        // for i = [2; n]
        // invariant : heap(1, i - 1)
        // min_sift_up(i)
        // heap(1, i)
        for index in 0..self.data.len() {
            self.min_sift_up(index);
        }
    }

    /// Ascending sort implementation based on recursive implementation of the big root heap
    ///
    /// ```rust
    /// use algorithms_rs::Heap;
    ///
    /// let mut max_heap = Heap::from_vector(&vec![5, 3, 7, 9, 10, 23, 45, 23, 12, 23, 0, 12, 32]).unwrap();
    ///
    /// max_heap.heap_sort_by_max_heap();
    ///
    /// assert_eq!(
    ///    max_heap.inner_vec().to_vec(),
    ///    vec![0, 3, 5, 7, 9, 10, 12, 12, 23, 23, 23, 32, 45]
    /// );
    /// ```
    pub fn heap_sort_by_max_heap(&mut self) {
        self.build_max_heap_by_max_heapify();
        for index in (1..self.data.len()).rev() {
            self.data.swap(0, index);
            self.size -= 1;
            self.max_heapify(0);
        }
    }

    /// Descending sort implementation based on recursive implementation of small root heap
    ///
    /// ```rust
    /// use algorithms_rs::Heap;
    ///
    /// let mut min_heap = Heap::from_vector(&vec![3, 2, 1, 0, 23, 34, 56, 11, 230, 12]).unwrap();
    ///
    /// min_heap.heap_sort_by_min_heap();
    ///
    /// assert_eq!(min_heap.inner_vec().to_vec(), vec![230, 56, 34, 23, 12, 11, 3, 2, 1, 0]);
    /// ```
    pub fn heap_sort_by_min_heap(&mut self) {
        self.build_min_heap_by_min_heapify();
        for index in (1..self.data.len()).rev() {
            self.data.swap(0, index);
            self.size -= 1;
            self.min_heapify(0);
        }
    }

Small root heap upward adjustment Non-recursive algorithm implementation

Examples found in repository?
src/heap.rs (line 298)
292
293
294
295
296
297
298
299
300

    pub fn build_min_heap_by_siftup(&mut self) {
        // for i = [2; n]
        // invariant : heap(1, i - 1)
        // min_sift_up(i)
        // heap(1, i)
        for index in 0..self.data.len() {
            self.min_sift_up(index);
        }
    }

Big root heap upward adjustment Non-recursive algorithm implementation

Examples found in repository?
src/heap.rs (line 270)
264
265
266
267
268
269
270
271
272

    pub fn build_max_heap_by_shift_up(&mut self) {
        // for i = [2; n]
        // invariant : heap(1, i - 1)
        // max_sift_up(i)
        // heap(1, i)
        for index in (0..self.data.len()).rev() {
            self.max_sift_up(index);
        }
    }

Small root heap downward adjustment Non-recursive algorithm implementation

Examples found in repository?
src/heap.rs (line 369)
358
359
360
361
362
363
364
365
366
367
368
369
370
371

    pub fn dec_sort_with_min_sift(&mut self) {
        // for (i = n; i >= 2; i --)
        // heap(1, i) && sorted(i + 1, n) && x[1..i] <= x[i+1..n]
        // swap(1, i)
        // heap(2, i - 1) && sorted(i, n) && x[1..i-1] <= x[i..n]
        // sift_down(i - 1)
        // heap(1, i - 1) && sorted(i, n) && x[1..i - 1] <= x[i..n]
        // build Min Heap by min siftup
        self.build_min_heap_by_siftup();
        for idx in (1..self.data.len()).rev() {
            self.data.swap(0, idx);
            self.min_sift_down(idx - 1);
        }
    }

Big root heap downward adjustment Non-recursive algorithm implementation

Examples found in repository?
src/heap.rs (line 395)
384
385
386
387
388
389
390
391
392
393
394
395
396
397

    pub fn asc_sort_with_max_sift(&mut self) {
        // for (i = n; i >= 2; i --)
        // heap(1, i) && sorted(i + 1, n) && x[1..i] <= x[i+1..n]
        // swap(1, i)
        // heap(2, i - 1) && sorted(i, n) && x[1..i-1] <= x[i..n]
        // sift_down(i - 1)
        // heap(1, i - 1) && sorted(i, n) && x[1..i - 1] <= x[i..n]
        // build Max heap by max shiftup
        self.build_max_heap_by_shift_up();
        for idx in (1..self.data.len()).rev() {
            self.data.swap(0, idx);
            self.max_sift_down(idx - 1);
        }
    }

Constructing a big root heap by recursive adjustment algorithm of big root heap

Examples found in repository?
src/heap.rs (line 317)
316
317
318
319
320
321
322
323

    pub fn heap_sort_by_max_heap(&mut self) {
        self.build_max_heap_by_max_heapify();
        for index in (1..self.data.len()).rev() {
            self.data.swap(0, index);
            self.size -= 1;
            self.max_heapify(0);
        }
    }

Construction of large root heap by non-recursive adjustment algorithm of large root heap

use algorithms_rs::Heap;

let mut max_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();

max_heap.build_max_heap_by_shift_up();

assert_eq!(max_heap.inner_vec().to_vec(), vec![5, 4, 2, 3, 1])
Examples found in repository?
src/heap.rs (line 392)
384
385
386
387
388
389
390
391
392
393
394
395
396
397

    pub fn asc_sort_with_max_sift(&mut self) {
        // for (i = n; i >= 2; i --)
        // heap(1, i) && sorted(i + 1, n) && x[1..i] <= x[i+1..n]
        // swap(1, i)
        // heap(2, i - 1) && sorted(i, n) && x[1..i-1] <= x[i..n]
        // sift_down(i - 1)
        // heap(1, i - 1) && sorted(i, n) && x[1..i - 1] <= x[i..n]
        // build Max heap by max shiftup
        self.build_max_heap_by_shift_up();
        for idx in (1..self.data.len()).rev() {
            self.data.swap(0, idx);
            self.max_sift_down(idx - 1);
        }
    }

Constructing rootlet heap by recursive adjustment algorithm of rootlet heap

Examples found in repository?
src/heap.rs (line 337)
336
337
338
339
340
341
342
343

    pub fn heap_sort_by_min_heap(&mut self) {
        self.build_min_heap_by_min_heapify();
        for index in (1..self.data.len()).rev() {
            self.data.swap(0, index);
            self.size -= 1;
            self.min_heapify(0);
        }
    }

Construction of rootlet heap by non-recursive adjustment algorithm of rootlet heap

 use algorithms_rs::Heap;

 let mut min_heap = Heap::from_vector(&vec![3, 2, 1, 4, 5]).unwrap();

 min_heap.build_min_heap_by_siftup();

 assert_eq!(min_heap.inner_vec().to_vec(), vec![1, 2, 3, 4, 5]);
Examples found in repository?
src/heap.rs (line 366)
358
359
360
361
362
363
364
365
366
367
368
369
370
371

    pub fn dec_sort_with_min_sift(&mut self) {
        // for (i = n; i >= 2; i --)
        // heap(1, i) && sorted(i + 1, n) && x[1..i] <= x[i+1..n]
        // swap(1, i)
        // heap(2, i - 1) && sorted(i, n) && x[1..i-1] <= x[i..n]
        // sift_down(i - 1)
        // heap(1, i - 1) && sorted(i, n) && x[1..i - 1] <= x[i..n]
        // build Min Heap by min siftup
        self.build_min_heap_by_siftup();
        for idx in (1..self.data.len()).rev() {
            self.data.swap(0, idx);
            self.min_sift_down(idx - 1);
        }
    }

Ascending sort implementation based on recursive implementation of the big root heap

use algorithms_rs::Heap;

let mut max_heap = Heap::from_vector(&vec![5, 3, 7, 9, 10, 23, 45, 23, 12, 23, 0, 12, 32]).unwrap();

max_heap.heap_sort_by_max_heap();

assert_eq!(
   max_heap.inner_vec().to_vec(),
   vec![0, 3, 5, 7, 9, 10, 12, 12, 23, 23, 23, 32, 45]
);

Descending sort implementation based on recursive implementation of small root heap

use algorithms_rs::Heap;

let mut min_heap = Heap::from_vector(&vec![3, 2, 1, 0, 23, 34, 56, 11, 230, 12]).unwrap();

min_heap.heap_sort_by_min_heap();

assert_eq!(min_heap.inner_vec().to_vec(), vec![230, 56, 34, 23, 12, 11, 3, 2, 1, 0]);

Descending sort implementation based on non-recursive implementation of small root heap

 use algorithms_rs::Heap;

 let mut min_heap =
 Heap::from_vector(&vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14]).unwrap();
 min_heap.dec_sort_with_min_sift();
 assert_eq!(
       min_heap.inner_vec().to_vec(),
        vec![14, 13, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
 );

Non-recursive implementation of ascending sort based on large root heap

 use algorithms_rs::Heap;

 let mut max_heap = Heap::from_vector(&vec![9, 8, 7, 6, 5, 5, 4, 3, 2, 1, 0]).unwrap();

 max_heap.asc_sort_with_max_sift();

 assert_eq!(max_heap.inner_vec().to_vec(), vec![0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]);

Trait Implementations§

Formats the value using the given formatter. Read more
Returns the “default value” for a type. Read more

Auto Trait Implementations§

Blanket Implementations§

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Should always be Self
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.