Достаточно ли частичного порядка, в отличие от общего порядка, чтобы построить кучу?
C ++ std :: priority_queue просто нужен частичный порядок. Но если его реализация двоичная куча, как это работает?
Например: предположим, у нас есть частично упорядоченный набор ( {a, b, c, x}, {c < b, b < a, c < a} ), x не имеет ничего общего с a, b, c, Тогда максимальная куча это:
layer 1: x
layer 2: b x
layer 3: x x a c
После операции pop, обычно в учебниках, то есть заменить корень на c и уменьшаем размер на 1. Затем нам нужно сложить дерево внизу, в корень:
layer 1: c
layer 2: b x
layer 3: x x a
Мы поменяемся c а также b как c < bне так ли? И что? У нас до сих пор нет действительной кучи, так как b < a, Но b Не могу видеть» a,
Решение
Требование к priority_queue является (§23.6.4 стандарта C ++), что компаратор определяет строгий, слабый порядок. Последнее определено в §25.4 / 4 следующим образом:
Термин строгий относится к требованию нерефлексивного отношения (! Comp (x, x) для всех x), а термин слаб к требованиям, которые не так сильны, как требования для общего порядка, но сильнее, чем для частичного порядка , Если мы определим эквивалент (a, b) как! Comp (a, b) && ! comp (b, a), то требования состоят в том, чтобы comp и эквивалентные оба были транзитивными отношениями:
— комп (а, б) && comp (b, c) подразумевает comp (a, c)
— экв (а, б) && эквив (b, с) подразумевает экв (а, в) [Примечание: при этих условиях можно показать, что
i) эквивалентное отношение эквивалентности
II) Comp индуцирует четко определенное отношение на классы эквивалентности, определенные по экв
iii) Индуцированное отношение является строгим полным порядком. — конец примечания]
Другими словами, определяемое компаратором отношение не обязательно должно быть полным, но оно должно быть полным по отношению к классам эквивалентности, определенным гипотетическим отношением equiv, который определяет все элементы как равные, которые не меньше или больше друг друга.
Говоря проще, любые элементы, не охваченные отношением сравнения, будут рассматриваться как равные.
Другие решения
Других решений пока нет …