c++ - 使用堆的优先级队列，具有相同键的值不遵循FIFO(先进先出)

Question

因此，我试图创建此优先级队列来处理我的“订单”对象，但我遇到了一个问题，即包含相同键/优先级的对象将放置在比其他先初始化的对象更早的位置。我已经提供了预期的和收到的输出，以及关于如何使用笔记构造堆的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

*/ 

Answer 1

来自以上回答信息的固定代码

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