Блог

Мне просто любопытно, могу ли я использовать какой-либо другой тип данных для присвоения приоритета? Например, строки, числа с плавающей точкой и т.д.?

Абстрактно, любой тип с разумным строгим слабым упорядочением может использоваться в качестве приоритета в приоритетной очереди. Используемый вами язык будет определять, как определить этот порядок: в C оператор < используется в стандартных контейнерах, в Java обычно используются интерфейс Comparable и функция compareTo. Также часто поддерживаются пользовательские функции сравнения, которые могут сравнивать элементы способом, отличным от стандартного.

Нет.

Упорядочивающий элемент приоритетной очереди не обязательно должен быть целым.

ДА.

Вы можете использовать любой тип, который вы хотите, при условии, что два значения этого типа могут сравниваться для определения их внутреннего порядка.

В принципе, вы можете создать очередь приоритетов, которая использует любой тип, который вы хотите, даже комплексное число, если вы можете определить порядок, который имеет смысл для них.

Однако здесь есть еще один, незаданный вопрос, на который ответ:

Да, большинство существующих реализаций приоритетной очереди будут использовать целое число в качестве элемента упорядочивания, поскольку это самое простое и наиболее распространенное значение, используемое для этой цели.

Вот полномасштабная демонстрация C того, как ставить в очередь SillyJobs, определяемая как

 struct SillyJob
{
    std::string description;
    std::string priority;
    // ...
};
  

Это делается двумя способами: с использованием члена operator< (по умолчанию) и путем передачи явного предиката сравнения priority_queue конструктору.

Давайте посмотрим на результат заранее:

 Silly: (by description length)
LOW: very very long description
HIGH: short
------------------------------------------------------------
Not so silly: (by priority value)
HIGH: short
LOW: very very long description
  

Смотрите это в прямом эфиреhttp://ideone.com/VEEQa

 #include <queue>
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <map>

struct SillyJob
{
    std::string description;
    std::string priority;

    SillyJob(const std::stringamp; d, const std::stringamp; p)
        : description(d), priority(p) { }

    bool operator<(const SillyJobamp; sj) const { return description.size() < sj.description.size(); }

    friend std::ostreamamp; operator<<(std::ostreamamp; os, const SillyJobamp; sj)
    { return os << sj.priority << ": " << sj.description; }
};

static bool by_priority(const SillyJobamp; a, const SillyJobamp; b)
{
    static std::map<std::string, int> prio_map;
    if (prio_map.empty())
    {
        prio_map["HIGH"]   = 3;
        prio_map["MEDIUM"] = 2;
        prio_map["LOW"]    = 1;
    }

    return prio_map[a.priority] < prio_map[b.priority];
}

int main()
{
    std::cout << "Silly: (by description length)" << std::endl;
    {
        // by description length (member operator<)
        std::priority_queue<SillyJob> silly_queue;

        silly_queue.push(SillyJob("short", "HIGH"));
        silly_queue.push(SillyJob("very very long description", "LOW"));

        while (!silly_queue.empty())
        {
            std::cout << silly_queue.top() << std::endl;
            silly_queue.pop();
        }
    }

    std::cout << std::string(60, '-') << "nNot so silly: (by priority value)" << std::endl;
    {
        // by description length (member operator<)
        typedef bool (*cmpf)(const SillyJobamp;, const SillyJobamp;);
        typedef std::priority_queue<SillyJob, std::vector<SillyJob>, cmpf> not_so_silly_queue;

        not_so_silly_queue queue(by_priority);

        queue.push(SillyJob("short", "HIGH"));
        queue.push(SillyJob("very very long description", "LOW"));

        while (!queue.empty())
        {
            std::cout << queue.top() << std::endl;
            queue.pop();
        }
    }

}
  

PS. by_priority Функция сравнения — довольно хороший пример плохого дизайна, но имейте в виду, что это было только в демонстрационных целях 🙂

Вы можете использовать любой тип для приоритета, если значения типа можно сравнить друг с другом.