Priority queue as heap in C++

Question

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:

in your upHeap you have unconditional break. It seems it should be inside else. (if current_priority < parent_priority swap, otherwise break) — Andrew Kashpur
@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
@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

Jim Mischel Jim Mischel · Accepted Answer · 2018-11-26T17:00:57

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.

Priority queue as heap in C++

1 Answers