Priority Queue using heap, values with same key don't follow FIFO (first in first out)

Question

So I'm trying to create this priority queue to handle my "Order" objects, I'm running into a problem where an object containing the same key/priority will be placed at an early earlier position than others initialized first. I have provided the expected and received output alongside the 83 lines of code of how I constructed my heap with notes

#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

*/

Now is a good time to learn how to use the debugger that is available for your compiler toolset. — PaulMcKenzie, May 29 '20 at 09:37
There is a "Debug" option on the main menu. Or just hit F10 and keep hitting F10./ F11 You will see the highlight move up (or down), executing a single line / function at a time. — PaulMcKenzie, May 29 '20 at 09:39
Heaps, don't follow FIFO. I had to add a third element for a tire breaker and implement it into my operator overloading for < when keys/priorities were equal — Brett, May 29 '20 at 10:45
is there a reason you don't use `std::priority_queue`, `std::push_heap` or `std::pop_heap`? — Caleth, May 29 '20 at 13:36
Possible duplicate of https://stackoverflow.com/q/57894388/56778 — Jim Mischel, May 29 '20 at 14:28

score 1 · Answer 1 · answered May 29 '20 at 10:50

Fixed code from answered information above

#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;
}

score 1 · Answer 2 · answered May 29 '20 at 10:54

In general, heap does not have FIFO property until you implement something that helps doing so. In your order class, you are only comparing using the priority value. In your Order class, you are comparing two Orders by only their priority value. You need a additional variable that serves as the purpose for recording the timing when that value was inserted, and compare according to that.

If you are using the variable value for that purpose, you need to specify in your overloaded < method, what do you want to do when two Order's priority values are equal. Currently, you are only using the priority variable to compare. You are not specifying what do you want to do when the priority of two Orders are equal. You have to specify what do you want to do when the priority value of two variables are equal. Maybe compare a timing variable.

Thank you so much, it worked! I was struggling on that for the longest time! I posted the changes to my code below — Brett, May 29 '20 at 10:58

Priority Queue using heap, values with same key don't follow FIFO (first in first out)

2 Answers2