Очередь приоритетов с использованием кучи, значения с одним и тем же ключом не следуют за FIFO (первым пришел - первым вышел) - PullRequest
Новая
       107

Очередь приоритетов с использованием кучи, значения с одним и тем же ключом не следуют за FIFO (первым пришел - первым вышел)

1 голос
/ 29 мая 2020

Итак, я пытаюсь создать эту приоритетную очередь для обработки моих объектов «Порядок», я столкнулся с проблемой, когда объект, содержащий тот же ключ / приоритет, будет помещен в более раннюю более раннюю позицию, чем другие инициализированные первыми. Я предоставил ожидаемый и полученный результат вместе с 83 строками кода того, как я построил свою кучу с примечаниями 

#include <iostream>
#include <vector>

struct Order {
    int value = -1;
    int priority = -1;
    bool operator <(Order const& RHS) { return priority < RHS.priority; } 
};

class heap {
private:
    std::vector<Order> orders{ Order{} };
    int size{}; //initalizes it at 0
    int p(int index) { return index >> 1; } 
    int l(int index) { return index << 1; } 
    int r(int index) { return (index << 1) + 1; } 
public:
    bool isEmpty() const { return size == 0; }
    void shiftUp(int position);
    void shiftDown(int position);
    void add(Order new_entry);
    Order removeTop();
    Order& getTop() { return orders[1]; }
}; 

template <typename T> 
void mySwap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

int main() {
    heap h;
    h.add(Order{1,3}); h.add(Order{2,2});
    h.add(Order{3,3}); h.add(Order{5,1});
    h.add(Order{6,2}); h.add(Order{7,2});
    h.add(Order{8,3}); h.add(Order{9,1});
    h.add(Order{23,3}); 
    std::cout << "value" << "     key(priority)" << "\n";
    for (int i = 0; i < 8; i++) {
        Order temp = h.removeTop();
        std::cout << temp.value << "\t    " << temp.priority << "\n";
    }
}

void heap::shiftUp(int position) {
    if (position > size) return; 
    if (position == 1) return; 
    if (orders[p(position)] < orders[position]) { 
        mySwap(orders[position], orders[p(position)]);
        shiftUp(p(position));
    }
}

void heap::shiftDown(int position) {
    if (position > size) return; 
    int greaterPosition = position;
    if (l(position) <= size && orders[position] < orders[l(position)]) 
        greaterPosition = l(position);
    if (r(position) <= size && orders[greaterPosition] < orders[r(position)]) 
        greaterPosition = r(position);
    if (greaterPosition != position) { 
        mySwap(orders[position], orders[greaterPosition]);
        shiftDown(greaterPosition);
    }
}

void heap::add(Order new_entry) {
    if (size + 1 >= orders.size()) orders.push_back(Order{}); 

    orders[++size] = new_entry; 
    shiftUp(size); 
}

Order heap::removeTop() {
    Order temp = orders[1];
    mySwap(orders[1],orders[orders.size() - 1]); size--; 
    orders.pop_back(); 
    shiftDown(1); 
    return temp;
}


/*
        Expected Output

    Value           key(priority)
    1                   3
    3                   3
    8                   3
    23                  3
    2                   2
    6                   2
    7                   2
    5                   1
    9                   1


    Recieved/wrong Output

    value            key(priority)
    1                   3
    23                  3
    3                   3
    8                   3
    2                   2
    6                   2
    7                   2
    5                   1

*/

Ответы [ 2 ]

1 голос
/ 29 мая 2020

В общем, куча не имеет свойства FIFO, пока вы не реализуете что-то, что помогает в этом. В вашем классе заказа вы сравниваете только с использованием значения приоритета. В вашем классе Order вы сравниваете два Orders только по их значению приоритета. Вам нужна дополнительная переменная, которая служит для записи времени, когда это значение было вставлено, и сравнивать в соответствии с этим.

Если вы используете переменную value для этой цели, вам нужно указать в ваш перегруженный метод <, что вы хотите делать, когда два значения Order's priority равны. В настоящее время для сравнения используется только переменная priority. Вы не указываете, что вы хотите делать, когда priority из двух Orders равны. Вы должны указать, что вы хотите делать, когда значения priority двух переменных равны. Может быть, сравнить временную переменную.

1 голос
/ 29 мая 2020

Фиксированный код из приведенной выше информации 

#include <iostream>
#include <vector>

struct Order {
    int value = -1;
    int priority = -1;
    int FIFO;
    bool operator <(Order const& RHS) {
        if (priority == RHS.priority)
            return FIFO > RHS.FIFO;
        else
            return priority < RHS.priority;
    } //compares keys for larger presidence 
};

class heap {
private:
    std::vector<Order> orders{ Order{} };
    int size{}; //initalizes it at 0
    int p(int index) { return index >> 1; } 
    int l(int index) { return index << 1; }  
    int r(int index) { return (index << 1) + 1; } 
public:
    bool isEmpty() const { return size == 0; }
    void shiftUp(int position);
    void shiftDown(int position);
    void add(Order new_entry);
    Order removeTop();
    Order& getTop() { return orders[1]; }
}; 

template <typename T> 
void mySwap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

int main() {
    heap h;
    h.add(Order{1,3}); h.add(Order{2,2});
    h.add(Order{3,3}); h.add(Order{5,1});
    h.add(Order{6,2}); h.add(Order{7,2});
    h.add(Order{8,3}); h.add(Order{9,1});
    h.add(Order{23,3}); 
    std::cout << "value" << "     key(priority)" << "\n";
    for (int i = 0; i < 8; i++) {
        Order temp = h.removeTop();
        std::cout << temp.value << "\t    " << temp.priority << "\n";
    }
}

void heap::shiftUp(int position) {
    if (position > size) return; 
    if (position == 1) return; 
    if (orders[p(position)] < orders[position]) { 
        mySwap(orders[position], orders[p(position)]);
        shiftUp(p(position));
    }
}

void heap::shiftDown(int position) {
    if (position > size) return; 
    int greaterPosition = position;
    if (l(position) <= size && orders[position] < orders[l(position)]) 
        greaterPosition = l(position);
    if (r(position) <= size && orders[greaterPosition] < orders[r(position)]) 
        greaterPosition = r(position);
    if (greaterPosition != position) { 
        mySwap(orders[position], orders[greaterPosition]);
        shiftDown(greaterPosition);
    }
}

void heap::add(Order new_entry) {
    if (size + 1 >= orders.size()) orders.push_back(Order{});
    new_entry.FIFO = size + 1;
    orders[++size] = new_entry; 
    shiftUp(size); 
}

Order heap::removeTop() {
    Order temp = orders[1];
    mySwap(orders[1],orders[orders.size() - 1]); size--; 
    orders.pop_back(); 
    shiftDown(1); 
    return temp;
}
...