Достаточно ли частичного порядка, в отличие от общего порядка, чтобы построить кучу?
C ++ std :: priority_queue просто нужен частичный порядок. Но если его реализацияbinary heap, как это работает?
Например: предположим, у нас есть частично упорядоченный набор( {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
.