概述
优先级队列是一种用来维护由一组元素构成集合S的数据结构，其中每个元素都有一个相关的值，称之为关键字。一个最小优先级队列支持以下操作：
insert(S,x):将元素x插入到集合S中min(S)：返回S中具有最小关键字的元素extract_min(S):去掉并返回S中具有最小关键字的元素decrease_key(S,x,k):将元素x的关键字值减小到k，这里的k的值小于x的原始关键字
相关
队列容量由
_data的大小来表征。默认将_data大小设为0；可以显式提供reseve_size参数来设置_data的大小。队列容量用于限制队列大小。一旦队列已满，则下一次插入之前会将队列容量增加一倍；一旦队列不足队列的1/4，则一旦执行
extract_min操作则将队列容量缩减至一半。两个特殊的可调用对象，这两个方法的引入使得最小优先级队列不仅可以应用于
class和struct类型，也可以应用于int,double等非类的类型
_getKey
- 一个
std::function<TKeyType&(std::shared_ptr<T>)>类型的对象，它可以接收std::shared_ptr<T>类型的参数，返回TKeyType类型的引用。- 其中队列保存的是T类型数据的强引用，
TKeyType是T类型数据的关键字类型。通过_getKey可以获取队列数据的关键字的引用。- 对于
class类型，TKeyType就是T对象的关键字类型，_getKey就是返回关键字的引用- 对于int等内置类型，
TKeyType就是T本身。_getKey就是返回它自身的引用_compare
- 一个
std::function<bool (std::shared_ptr<T>,std::shared_ptr<T>)>类型的对象，它用于队列中两个数据的大小比较。
实现
|
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 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 |
template<typename T,typename TKeyType> class MinQueue { public: //一个可调用对象类型，该类型的对象可用于比较两个std::shared_ptr<T>的小于比较 typedef std::function<bool (std::shared_ptr<T>,std::shared_ptr<T>)> CompareType; //一个可调用对象，该类型的对象可用于获取std::shared_ptr<T>的关键字, //并修改该关键字（返回的是关键字的引用 typedef std::function<TKeyType&(std::shared_ptr<T>)> GetKeyType; //显示构造 MinQueue(CompareType compare,GetKeyType getKey):_size(0),_compare(compare),_getKey(getKey) { } //显示构造 MinQueue(std::size_t reseve_size,CompareType compare,GetKeyType getKey):_size(0),_compare(compare),_getKey(getKey) { _data.resize(reseve_size); } //最小值 //根据最小堆的性质，队列的第一个值就是最小值的强引用。如果队列为空，则返回一个空引用 std::shared_ptr<T> min() { if(!_size) return std::shared_ptr<T>(); return _data[0]; } //删除队列中最小值，并返回最小值 //根据最小堆的性质，队列的第一个值就是最小值的强引用。 //- 如果队列为空，则返回一个空引用 //- 如果队列非空，则执行以下操作： // - 交换队列的第一个元素和最后一个元素 // - 队列的`_size`自减 // - 此时队列的首个元素违反了最小堆性质，因此执行`heapify(0)`保持性质 // - 返回旧的首个元素 //一旦队列长度不足容量的1/4，则将队列容量设置为队列长度的一倍 std::shared_ptr<T> extract_min() { if(!_size) return std::shared_ptr<T>(); auto result = _data[0]; _data[0] = _data[_size-1]; _size--; heapify(0); if(_size <= _data.size()/4) _data.resize(_size*2+2); return result; } //向队列中插入一个元素 //插入之前首先判断队列是否已满。若队列已满，则将`_data`扩容为大小`_size*2+2` int insert(std::shared_ptr<T> element) { if (!element) return -1; if (_size == _data.size()) _data.resize(_size*2+2); int index = _size; _size++; _data[index] = element; TKeyType& k = _getKey(element); TKeyType old_k = k; k = unlimit<TKeyType>(); decreate_key(index,old_k); return index; } //是否为空 bool is_empty() { return _size == 0; } //返回指定元素是否在队列中 int index_inqueue(std::shared_ptr<T> element) { if(!element) throw std::invalid_argument("is_inqueue error: element must not be nullptr"); for (std::size_t index = 0;index < _size;index++) { if(element == _data[index]) return index; } return -1; } //缩减队列中某元素的key值 void decreate_key(std::size_t element_index,TKeyType new_key) { if (element_index >= _size) throw std::invalid_argument("decreat_key error: element_index must < _size"); if (new_key > _getKey(_data.at(element_key))) throw std::invalid_argument("decreat_key error: new_key > curr_key"); _getKey(_data.at(element_index)) = new_key; bool valid; while(element_index != 0) { auto pIndex } } //建堆 void setupHeap() { if (_size <= 1) return; int index = (_size - 1)/2; while(index >= 0) { heapify(index); index--; } } //维护堆特性 void heapify(std::size_t elementIndex) { if (elementIndex >= _size) return; auto minIndex = elementIndex; bool left_valid = true; bool right_valid = true; auto leftIndex = _lchildIndex(elementIndex,left_valid); auto rightIndex = _rchildIndex(elementIndex,right_valid); if(left_valid) { if(_compare(_data.at(leftIndex),_data.at(minIndex))) minIndex = leftIndex; } if (right_valid) { if(_compare(_data.at(rightIndex),_data.at(minIndex))) minIndex = rightIndex; } if (minIndex != elementIndex) { std::swap(_data.at(elementIndex),_data.at(minIndex)); heapify(minIndex); } } protected: //返回一个节点的父节点位置 //根据最小堆的性质，一个子节点elementIndex的父节点是它的位置(elementIndex-1)/2。 std::size_t _parentIndex(std::size_t elementIndex,bool& valid) { if (elementIndex >= _size) { valid = false; return 0; } valid = true; if (elementIndex == 0) return 0;//根节点的父节点是自己 else return (elementIndex-1)>>1; } //返回一个节点的左子节点位置 //根据最小堆的性质，一个节点elementIndex的左子节点是它的位置(elementIndex/2)+1 std::size_t _lchildIndex(std::size_t elementIndex,bool& valid) { if (_size<2) { valid = false;//数组元素太少 return 0; } if (elementIndex>((_size-2)>>1)) { valid = false;//超出范围 return 0; } valid = true; return (elementIndex<<1)+1; } //返回一个节点的右子节点位置 //根据最小堆的性质，一个节点elementIndex的右子节点是它的位置(elementIndex/2)+2 std::size_t _rchildIndex(std::size_t elementIndex,bool& valid) { if (_size < 3) { valid = false;//数组元素太少 return 0; } if (elementIndex > ((_size-3)>>1)) { valid = false;//超出范围 return 0; } valid = true; return (elementIndex<<1)+1; } private: std::vector<std::shared_ptr<T>> _data;//最小优先级队列的数据 std::size_t _size;//堆大小 CompareType _compare;//可调用对象，用于两个shared_ptr<T>的小于比较 GetKeyType _getKey;//可调用对象，用于获取shared_ptr<T>的关键字，并修改关键字 }; |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
