rs_graph/collections/priqueue/
binheap.rs

1// Copyright (c) 2016 2017, 2020, 2022 Frank Fischer <frank-fischer@shadow-soft.de>
2//
3// This program is free software: you can redistribute it and/or
4// modify it under the terms of the GNU General Public License as
5// published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful, but
9// WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11// General Public License for more details.
12//
13// You should have received a copy of the GNU General Public License
14// along with this program.  If not, see  <http://www.gnu.org/licenses/>
15//
16
17//! Binary heap implementation
18
19use crate::collections::ItemPriQueue;
20
21use num_traits::{FromPrimitive, ToPrimitive};
22
23/// Heap item information.
24struct BinHeapItem<K, V, ID> {
25    /// The key associated with this item.
26    key: K,
27    /// The value (priority) of the item.
28    value: V,
29    /// Position of this element on the heap. If this element is *not*
30    /// on the heap, its the index of the next element in the free
31    /// list.
32    pos: ID,
33}
34
35/// Simply binary heap data structure.
36pub struct BinHeap<K, V, ID = u32> {
37    /// The heap elements.
38    heap: Vec<ID>,
39    /// The key and heap-index for each element.
40    data: Vec<BinHeapItem<K, V, ID>>,
41    /// First free item.
42    free: Option<ID>,
43}
44
45impl<K, V, ID> BinHeap<K, V, ID> {
46    pub fn new() -> Self {
47        Default::default()
48    }
49}
50
51impl<K, V, ID> Default for BinHeap<K, V, ID> {
52    fn default() -> Self {
53        BinHeap {
54            heap: vec![],
55            data: vec![],
56            free: None,
57        }
58    }
59}
60
61impl<K, V, ID> ItemPriQueue<K, V> for BinHeap<K, V, ID>
62where
63    K: Clone,
64    V: PartialOrd + Clone,
65    ID: FromPrimitive + ToPrimitive + Copy + Eq,
66{
67    type Item = ID;
68
69    fn clear(&mut self) {
70        self.heap.clear();
71        self.data.clear();
72        self.free = None;
73    }
74
75    fn is_empty(&self) -> bool {
76        self.heap.is_empty()
77    }
78
79    fn value(&self, item: &ID) -> &V {
80        &self.data[item.to_usize().unwrap()].value
81    }
82
83    fn push(&mut self, key: K, value: V) -> ID {
84        let item = if let Some(item) = self.free {
85            let idx = item.to_usize().unwrap();
86            // take from free list
87            let next = self.data[idx].pos;
88            if next == item {
89                self.free = None
90            } else {
91                self.free = Some(next)
92            }
93            // store data
94            self.data[idx] = BinHeapItem {
95                key,
96                value,
97                pos: ID::from_usize(self.heap.len()).unwrap(),
98            };
99            item
100        } else {
101            let item = ID::from_usize(self.data.len()).unwrap();
102            self.data.push(BinHeapItem {
103                key,
104                value,
105                pos: ID::from_usize(self.heap.len()).unwrap(),
106            });
107            item
108        };
109        self.heap.push(item);
110        self.upheap(item);
111        item
112    }
113
114    fn decrease_key(&mut self, item: &mut ID, value: V) -> bool {
115        let idx = item.to_usize().unwrap();
116        if self.data[idx].value > value {
117            self.data[idx].value = value;
118            self.upheap(*item);
119            true
120        } else {
121            false
122        }
123    }
124
125    fn pop_min(&mut self) -> Option<(K, V)> {
126        if self.heap.is_empty() {
127            return None;
128        }
129
130        // remove the smallest element from the heap
131        let min_item = self.heap.swap_remove(0);
132        let min_idx = min_item.to_usize().unwrap();
133        // put its data slot in the free list
134        if let Some(next) = self.free {
135            // free list is not empty
136            self.data[min_idx].pos = next;
137        } else {
138            // free list has been empty, this is the first element
139            self.data[min_idx].pos = min_item;
140        }
141        self.free = Some(min_item);
142
143        if !self.heap.is_empty() {
144            let n = self.heap.len();
145            let item = *self.heap.first().unwrap();
146            let idx = item.to_usize().unwrap();
147            let value = self.data[idx].value.clone();
148            let mut cur_pos = 0;
149            loop {
150                let left_pos = 2 * cur_pos + 1;
151                let right_pos = left_pos + 1;
152                let (next_pos, next_idx) = if left_pos >= n {
153                    break;
154                } else if right_pos >= n {
155                    (left_pos, self.heap[left_pos].to_usize().unwrap())
156                } else {
157                    let left_idx = self.heap[left_pos].to_usize().unwrap();
158                    let right_idx = self.heap[right_pos].to_usize().unwrap();
159                    if self.data[left_idx].value < self.data[right_idx].value {
160                        (left_pos, left_idx)
161                    } else {
162                        (right_pos, right_idx)
163                    }
164                };
165
166                if value <= self.data[next_idx].value {
167                    break;
168                }
169
170                self.heap[cur_pos] = self.heap[next_pos];
171                self.data[next_idx].pos = ID::from_usize(cur_pos).unwrap();
172                cur_pos = next_pos;
173            }
174            self.heap[cur_pos] = item;
175            self.data[idx].pos = ID::from_usize(cur_pos).unwrap();
176        }
177        Some((self.data[min_idx].key.clone(), self.data[min_idx].value.clone()))
178    }
179}
180
181impl<K, V, ID> BinHeap<K, V, ID>
182where
183    V: PartialOrd + Clone,
184    ID: FromPrimitive + ToPrimitive + Clone + Eq,
185{
186    /// Move the element `item` up in the heap until its parent does not have a
187    /// larger key or the root node is reached.
188    ///
189    /// Note that this function assumes that its value is smaller than the value
190    /// of its children.
191    fn upheap(&mut self, item: ID) {
192        let idx = item.to_usize().unwrap();
193        let value = self.data[idx].value.clone();
194        let mut cur_pos = self.data[idx].pos.to_usize().unwrap();
195        while cur_pos > 0 {
196            let parent_pos = (cur_pos - 1) / 2;
197            let parent_idx = self.heap[parent_pos].to_usize().unwrap();
198            // We could have used >=, too, but using >
199            // moves the item up the heap as far as possible. This results the
200            // last node touched with the same value to be considered next (to a
201            // certain extend) making the search more dfs like.
202            if value > self.data[parent_idx].value {
203                break;
204            }
205            self.heap[cur_pos] = self.heap[parent_pos].clone();
206            self.data[parent_idx].pos = ID::from_usize(cur_pos).unwrap();
207            cur_pos = parent_pos;
208        }
209        self.data[idx].pos = ID::from_usize(cur_pos).unwrap();
210        self.heap[cur_pos] = item;
211    }
212}
rs_graph/collections/priqueue/binheap.rs

rs_graph/collections/priqueue/
binheap.rs
