c++ - 优先级队列作为 C++ 中的堆
问题描述
我知道有一些类似的问题,但遗憾的是没有一个真正符合我的问题......所以我应该创建一个优先队列作为堆。我们已经得到了一些代码片段(相当伪代码)来使用,但是如果我打印树,我不会得到正确的数字。
我目前只是试图将随机数插入队列并打印它们。队列元素是一个名为 Queue_elem 的自定义类。这是我的插入功能:
void Queue::insert(Queue_elem item){
this->container[number_elements] = item;
if (this->number_elements > 0) this->upHeap();
this->number_elements++;
}
number_elements 是数组(容器)大小的计数器。这是我的upHeap:
void Queue::upHeap(){
for (int i = this->number_elements; i>=0; i = (i-1)/2) {
int parent = (i-1)/2;
if (this->container[i].getPriority() < this->container[parent].getPriority()) {
swap(this->container[i], this->container[parent]);
}
break;
}
}
就是这样。在我的主要内容中,我正在插入随机值并尝试像这样打印它们:
Queue que(11);
mt19937 rng;
rng.seed(random_device()());
uniform_int_distribution<std::mt19937::result_type> dist6(1,50);
for (int i = 0; i < 10; ++i) {
Queue_elem tmp(dist6(rng));
que.insert(tmp);
}
cout << que.container[0].getPriority() << endl;
for (int i = 0; i < 5;i++) {
cout << que.container[(2*i)+1].getPriority() << endl;
cout << que.container[(2*i)+2].getPriority() << endl;
}
所以我一个一个地遍历树,以正确的顺序打印数组,但这总是错误的......
如有必要,我也可以提供整个项目。提前感谢一堆。
编辑:Queue_elem
class Queue_elem {
public:
Queue_elem();
Queue_elem(int prio);
virtual ~Queue_elem();
int getPriority();
void setPriority(int prio);
int getId();
private:
int id;
int priority;
};
编辑2:输出是这样的:
1
18
29
26
37
30
44
46
48
49
0
解决方案
我看不出有什么问题。您显示的输出对应于此堆:
1
18 29
26 37 30 44
46 48 49
这是一个有效的最小堆。每个子节点都大于其父节点。请记住,在堆中,项目不一定是排序的。
最后得到 0 的原因是因为您正在尝试打印没有右子节点的节点的右子节点。
推荐阅读
- excel - UDF Excel 使用 Vlookup?JavaScript API
- javascript - 删除数组开头和结尾的 null
- firebase - 在横向模式下调用时未调用 createSignInIntentBuilder() 的 onActivityResult
- java - Java流,获取对象列表的映射
- python - 元素引发 TimeoutException
- javascript - 页面重新加载后来自 JS 的按钮单击仅有效不能始终如一地工作
- php - PHP AJAX HTML:在 foreach 循环中更改唯一表数据
- flutter - 如何从 SliverPersistentHeader 中删除海拔?
- python - 遍历整数列以查看该值是否包含在不同列的范围内
- javascript - 如何使用 keydown 事件移动列表项