c++实现优先队列 |
您所在的位置：网站首页 › 如何实现优先队列运行的方法 › c++实现优先队列 |
|
优先队列 优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。 典型实现 出于性能考虑，优先队列用堆来实现，具有O(log n)时间复杂度的插入元素性能，O(n)的初始化构造的时间复杂度。如果使用自平衡二叉查找树，插入与删除的时间复杂度为O(log n)，构造二叉树的时间复杂度为O(n log n)。从计算复杂度的角度，优先级队列等价于排序算法。 代码示例 (详情见代码注释) #include using namespace std; class PriorityQueue { private: int* pArray; int m_length; public: PriorityQueue(int N) { // 为后续根节点直接从1开始作准备 pArray = new int[N + 1]; m_length = 0; } int delMax() { // 大根堆第一个元素为最大 int max = pArray[1]; // 将第一个元素和最后一个元素交换,并使长度减一，即删除最大的元素 swap(pArray[1], pArray[m_length--]); // 防止对象游离 pArray[m_length + 1] = NULL; // 下沉恢复堆的有序性 sink(1); // 返回最大的节点值 return max; } void insert(int v) { // 将值v插入到pArray[1]位置处，所以这里用的前置++ pArray[++m_length] = v; // 新加入的元素上浮 swim(m_length); } // 判断是否为空 bool isEmpty() { return m_length == 0; } int size() { return m_length; } // 向上浮 void swim(int k) { // 判断最下层的叶子节点值如果大于其父节点则进入循环上浮 while (k > 1 && pArray[k] > pArray[k / 2]) { // 交换父节点和子节点 swap(pArray[k / 2], pArray[k]); // k数值减小继续向上浮 k /= 2; } } // 向下沉 void sink(int k) { while (2 * k pArray[j]) break; // 如果父节点比子节点小则交换 swap(pArray[k], pArray[j]); // k值变大继续下沉 k = j; } } }; int main() { PriorityQueue pq(5); pq.insert(2); pq.insert(11); pq.insert(6); pq.insert(1); pq.insert(15); cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |