не удалось сортировать в очереди приоритетов после удаления и изменения значения переменной объекта [duplicate]
В большинстве дистрибутивов у вас есть возможность установить еще одну версию gcc и g ++ у самого последнего компилятора, такого как gcc-4.7. Кроме того, большинство систем сборки знают о переменных среды CC и CXX, которые позволяют указать другие компиляторы C и C ++ соответственно. Я предлагаю что-то вроде:
CC=gcc-4.4 CXX=g++-4.4 cmake path/to/your/CMakeLists.txt
Для Make-файлов должен быть аналогичный способ. Я не рекомендую устанавливать настраиваемые символические ссылки в / usr / local, если вы не знаете, что делаете.
5 ответов
Сначала предположим, что он, вероятно, пересекает данные в том порядке, в котором он хранится. Чтобы свести к минимуму время вставки элемента в очередь, он обычно не сохраняет все элементы в отсортированном порядке.
PriorityQueues реализованы с использованием двоичной кучи. Куча не является сортированной структурой и частично упорядочена. Каждый элемент имеет «приоритет», связанный с ним. Используя кучу для реализации очереди приоритетов, она всегда будет иметь элемент с наивысшим приоритетом в корневом узле кучи. поэтому в очереди приоритетов элемент с высоким приоритетом обслуживается перед элементом с низким приоритетом. Если два элемента имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди. Куча обновляется после каждого удаления элементов для сохранения свойства кучи
Двоичные кучи - эффективный способ реализации очередей приоритетов. Единственная гарантия порядка, которую делает куча, состоит в том, что элемент наверху имеет наивысший приоритет (возможно, это «самый большой» или «самый маленький» в соответствии с каким-то порядком). Куча - это двоичное дерево, обладающее свойствами: Свойство Shape: дерево заполняется сверху вниз слева направо. Order prperty: элемент на любом узле больше (или меньше, если наименьший имеет наивысший приоритет), чем его два дочерних узла. Когда итератор посещает все элементы, он, вероятно, делает это в обход уровня, то есть он посещает каждый узел на каждом уровне, прежде чем перейти на следующий уровень. Поскольку единственная гарантия порядка, заключающаяся в том, что узел имеет более высокий приоритет, чем его дочерние элементы, узлы на каждом уровне не будут иметь особого порядка.
-
1Это не совсем правильно. Куча также имеет гарантию, что x [i] & lt; = x [2i] & lt; = x [2i + 1]. – user207421 25 January 2011 в 01:18
Хорошо, как говорит Джавадок, так оно и было реализовано. Вероятно, очередь приоритетов использует двоичную кучу в качестве базовой структуры данных. Когда вы удаляете элементы, куча переопределяется, чтобы сохранить свойство кучи.
Во-вторых, нецелесообразно связывать определенную реализацию (форсирование упорядоченного порядка). При текущей реализации вы можете свободно перемещаться по нему в любом порядке и использовать любую реализацию.