Приоритетная очередь как куча в C ++ - PullRequest
Новая
       14

Приоритетная очередь как куча в C ++

0 голосов
/ 23 ноября 2018

Я знаю, что есть подобные вопросы, но, к сожалению, ни один из них не соответствует моей проблеме ... Поэтому я должен создать очередь с приоритетами в виде кучи.Нам даны некоторые фрагменты кода (скорее псевдокод), но если я распечатаю дерево, я не получу правильные числа.

В настоящее время я просто пытаюсь вставить случайные числа вочереди и распечатать их.Элемент очереди - это пользовательский класс с именем 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 Ответ

0 голосов
/ 26 ноября 2018

Я не вижу проблемы.Вывод, который вы показываете, соответствует этой куче: 

              1
      18             29
  26      37     30      44
46  48  49

Это допустимая минимальная куча.Каждый дочерний узел больше, чем его родитель.Помните, что в куче элементы не обязательно сортируются.

Причина, по которой вы получаете 0 в конце, заключается в том, что вы пытаетесь напечатать правильный дочерний элемент узла, у которого нет правого дочернего элемента.

...