Priority queue as heap in C++
I know there are some similar questions like this, but sadly none of them really match my problem... So I'm supposed to create a priority queue as heap. We've been given some code snippets (rather pseudo code) to use, but if I print the tree, I won't get the correct numbers.
I'm currently just trying to insert random numbers into the queue and print them. A queue element is a custom class named Queue_elem. This is my insert function:
void Queue::insert(Queue_elem item){
this->container[number_elements] = item;
if (this->number_elements > 0) this->upHeap();
this->number_elements++;
}
number_elements is the counter for the size of the array (container). Here is my 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;
}
}
And that's it. In my main I'm inserting random values and try to print them like this:
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;
}
So I'm going through the tree child by child to print the array in the correct order, but it's always wrong...
I can also provide the whole project if necessary. Thanks a bunch in advance.
Edit: 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;
};
Edit 2: The output is this:
1
18
29
26
37
30
44
46
48
49
0
c++ binary-tree heap priority-queue
asked Nov 23 '18 at 8:49
BladeBlade
327
|
show 8 more comments
I know there are some similar questions like this, but sadly none of them really match my problem... So I'm supposed to create a priority queue as heap. We've been given some code snippets (rather pseudo code) to use, but if I print the tree, I won't get the correct numbers.
I'm currently just trying to insert random numbers into the queue and print them. A queue element is a custom class named Queue_elem. This is my insert function:
void Queue::insert(Queue_elem item){
this->container[number_elements] = item;
if (this->number_elements > 0) this->upHeap();
this->number_elements++;
}
number_elements is the counter for the size of the array (container). Here is my 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;
}
}
And that's it. In my main I'm inserting random values and try to print them like this:
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;
}
So I'm going through the tree child by child to print the array in the correct order, but it's always wrong...
I can also provide the whole project if necessary. Thanks a bunch in advance.
Edit: 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;
};
Edit 2: The output is this:
1
18
29
26
37
30
44
46
48
49
0
c++ binary-tree heap priority-queue
asked Nov 23 '18 at 8:49
BladeBlade
327
Why are you not using std::priority_queue?
– user743414
Nov 23 '18 at 8:53
Could you Post theQueue_elemdefinition Class?
– Blood-HaZaRd
Nov 23 '18 at 8:58
in your upHeap you have unconditional break. It seems it should be inside else. (if current_priority < parent_priority swap, otherwise break)
– Andrew Kashpur
Nov 23 '18 at 9:08
1
@Blade What does "incorrect" mean here? It sounds like you are expecting your loop to give you all ten numbers in a sorted order. This structure gives you the correct value at the head of the queue. Instead take the head of the queue, print it, remove it, repeat
– janm
Nov 23 '18 at 9:57
1
@janm Okay so I drew the binary tree and indeed there was one higher number before a lower one, because it was just in the node next to it's parent. So the heap condition is still fulfilled. Everything seems to work perfectly fine now, thanks!
– Blade
Nov 23 '18 at 13:13
|
show 8 more comments
I know there are some similar questions like this, but sadly none of them really match my problem... So I'm supposed to create a priority queue as heap. We've been given some code snippets (rather pseudo code) to use, but if I print the tree, I won't get the correct numbers.
I'm currently just trying to insert random numbers into the queue and print them. A queue element is a custom class named Queue_elem. This is my insert function:
void Queue::insert(Queue_elem item){
this->container[number_elements] = item;
if (this->number_elements > 0) this->upHeap();
this->number_elements++;
}
number_elements is the counter for the size of the array (container). Here is my 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;
}
}
And that's it. In my main I'm inserting random values and try to print them like this:
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;
}
So I'm going through the tree child by child to print the array in the correct order, but it's always wrong...
I can also provide the whole project if necessary. Thanks a bunch in advance.
Edit: 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;
};
Edit 2: The output is this:
1
18
29
26
37
30
44
46
48
49
0
c++ binary-tree heap priority-queue
asked Nov 23 '18 at 8:49
BladeBlade
327
I know there are some similar questions like this, but sadly none of them really match my problem... So I'm supposed to create a priority queue as heap. We've been given some code snippets (rather pseudo code) to use, but if I print the tree, I won't get the correct numbers.
I'm currently just trying to insert random numbers into the queue and print them. A queue element is a custom class named Queue_elem. This is my insert function:
void Queue::insert(Queue_elem item){
this->container[number_elements] = item;
if (this->number_elements > 0) this->upHeap();
this->number_elements++;
}
number_elements is the counter for the size of the array (container). Here is my 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;
}
}
And that's it. In my main I'm inserting random values and try to print them like this:
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;
}
So I'm going through the tree child by child to print the array in the correct order, but it's always wrong...
I can also provide the whole project if necessary. Thanks a bunch in advance.
Edit: 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;
};
Edit 2: The output is this:
1
18
29
26
37
30
44
46
48
49
0
c++ binary-tree heap priority-queue
c++ binary-tree heap priority-queue
asked Nov 23 '18 at 8:49
BladeBlade
327
asked Nov 23 '18 at 8:49
BladeBlade
327
edited Nov 23 '18 at 9:55
Blade
asked Nov 23 '18 at 8:49
BladeBlade
327
asked Nov 23 '18 at 8:49
BladeBlade
327
asked Nov 23 '18 at 8:49
BladeBlade
327
327
Why are you not using std::priority_queue?
– user743414
Nov 23 '18 at 8:53
Could you Post theQueue_elemdefinition Class?
– Blood-HaZaRd
Nov 23 '18 at 8:58
in your upHeap you have unconditional break. It seems it should be inside else. (if current_priority < parent_priority swap, otherwise break)
– Andrew Kashpur
Nov 23 '18 at 9:08
1
@Blade What does "incorrect" mean here? It sounds like you are expecting your loop to give you all ten numbers in a sorted order. This structure gives you the correct value at the head of the queue. Instead take the head of the queue, print it, remove it, repeat
– janm
Nov 23 '18 at 9:57
1
@janm Okay so I drew the binary tree and indeed there was one higher number before a lower one, because it was just in the node next to it's parent. So the heap condition is still fulfilled. Everything seems to work perfectly fine now, thanks!
– Blade
Nov 23 '18 at 13:13
|
show 8 more comments
Why are you not using std::priority_queue?
– user743414
Nov 23 '18 at 8:53
Could you Post theQueue_elemdefinition Class?
– Blood-HaZaRd
Nov 23 '18 at 8:58
in your upHeap you have unconditional break. It seems it should be inside else. (if current_priority < parent_priority swap, otherwise break)
– Andrew Kashpur
Nov 23 '18 at 9:08
1
@Blade What does "incorrect" mean here? It sounds like you are expecting your loop to give you all ten numbers in a sorted order. This structure gives you the correct value at the head of the queue. Instead take the head of the queue, print it, remove it, repeat
– janm
Nov 23 '18 at 9:57
1
@janm Okay so I drew the binary tree and indeed there was one higher number before a lower one, because it was just in the node next to it's parent. So the heap condition is still fulfilled. Everything seems to work perfectly fine now, thanks!
– Blade
Nov 23 '18 at 13:13
Why are you not using std::priority_queue?
– user743414
Nov 23 '18 at 8:53
Why are you not using std::priority_queue?
– user743414
Nov 23 '18 at 8:53
Could you Post the
Queue_elem definition Class?– Blood-HaZaRd
Nov 23 '18 at 8:58
Could you Post the
Queue_elem definition Class?– Blood-HaZaRd
Nov 23 '18 at 8:58
in your upHeap you have unconditional break. It seems it should be inside else. (if current_priority < parent_priority swap, otherwise break)
– Andrew Kashpur
Nov 23 '18 at 9:08
in your upHeap you have unconditional break. It seems it should be inside else. (if current_priority < parent_priority swap, otherwise break)
– Andrew Kashpur
Nov 23 '18 at 9:08
1
1
@Blade What does "incorrect" mean here? It sounds like you are expecting your loop to give you all ten numbers in a sorted order. This structure gives you the correct value at the head of the queue. Instead take the head of the queue, print it, remove it, repeat
– janm
Nov 23 '18 at 9:57
@Blade What does "incorrect" mean here? It sounds like you are expecting your loop to give you all ten numbers in a sorted order. This structure gives you the correct value at the head of the queue. Instead take the head of the queue, print it, remove it, repeat
– janm
Nov 23 '18 at 9:57
1
1
@janm Okay so I drew the binary tree and indeed there was one higher number before a lower one, because it was just in the node next to it's parent. So the heap condition is still fulfilled. Everything seems to work perfectly fine now, thanks!
– Blade
Nov 23 '18 at 13:13
@janm Okay so I drew the binary tree and indeed there was one higher number before a lower one, because it was just in the node next to it's parent. So the heap condition is still fulfilled. Everything seems to work perfectly fine now, thanks!
– Blade
Nov 23 '18 at 13:13
|
show 8 more comments
1 Answer
1
active
oldest
votes
I don't see a problem. The output you show corresponds to this heap:
1
18 29
26 37 30 44
46 48 49
That's a valid min-heap. Every child node is larger than its parent. Remember, in a heap, items aren't necessarily sorted.
The reason you're getting a 0 at the end is because you're trying to print the right child of a node that has no right child.
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53443308%2fpriority-queue-as-heap-in-c%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I don't see a problem. The output you show corresponds to this heap:
1
18 29
26 37 30 44
46 48 49
That's a valid min-heap. Every child node is larger than its parent. Remember, in a heap, items aren't necessarily sorted.
The reason you're getting a 0 at the end is because you're trying to print the right child of a node that has no right child.
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
add a comment |
I don't see a problem. The output you show corresponds to this heap:
1
18 29
26 37 30 44
46 48 49
That's a valid min-heap. Every child node is larger than its parent. Remember, in a heap, items aren't necessarily sorted.
The reason you're getting a 0 at the end is because you're trying to print the right child of a node that has no right child.
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
add a comment |
I don't see a problem. The output you show corresponds to this heap:
1
18 29
26 37 30 44
46 48 49
That's a valid min-heap. Every child node is larger than its parent. Remember, in a heap, items aren't necessarily sorted.
The reason you're getting a 0 at the end is because you're trying to print the right child of a node that has no right child.
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
I don't see a problem. The output you show corresponds to this heap:
1
18 29
26 37 30 44
46 48 49
That's a valid min-heap. Every child node is larger than its parent. Remember, in a heap, items aren't necessarily sorted.
The reason you're getting a 0 at the end is because you're trying to print the right child of a node that has no right child.
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
answered Nov 26 '18 at 17:00
Jim MischelJim Mischel
106k12128247
106k12128247
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53443308%2fpriority-queue-as-heap-in-c%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Why are you not using std::priority_queue?
– user743414
Nov 23 '18 at 8:53
Could you Post the
Queue_elemdefinition Class?– Blood-HaZaRd
Nov 23 '18 at 8:58
in your upHeap you have unconditional break. It seems it should be inside else. (if current_priority < parent_priority swap, otherwise break)
– Andrew Kashpur
Nov 23 '18 at 9:08
1
@Blade What does "incorrect" mean here? It sounds like you are expecting your loop to give you all ten numbers in a sorted order. This structure gives you the correct value at the head of the queue. Instead take the head of the queue, print it, remove it, repeat
– janm
Nov 23 '18 at 9:57
1
@janm Okay so I drew the binary tree and indeed there was one higher number before a lower one, because it was just in the node next to it's parent. So the heap condition is still fulfilled. Everything seems to work perfectly fine now, thanks!
– Blade
Nov 23 '18 at 13:13