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

Question

所以我正在尝试创建这个优先级队列来处理我的"Order"对象，我遇到了一个问题，即包含相同键/优先级的对象将被放置在比其他人更早的位置首先初始化。我已经提供了预期和收到的输出以及 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;
}

Answer 2

通常，堆没有 FIFO 属性，直到您实现有助于这样做的东西。在您的订单类中，您仅使用优先级值进行比较。在Order类中，您仅通过优先级值比较两个Orders。您需要一个附加变量，用于记录插入该值的时间，并根据该变量进行比较。

如果您为此目的使用变量value，则需要在重载<方法中指定当两个Order'spriority值相等时要执行的操作。目前，您仅使用priority变量进行比较。您没有指定当两个Orders的priority相等时要执行的操作。您必须指定当两个变量的priority值相等时要执行的操作。也许比较一个时序变量。