Приоритет очереди приоритетов всегда должен быть интегральным?

Question

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

Answer 1

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

Answer 2

Вот демонстрация 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::string& d, const std::string& p)
        : description(d), priority(p) { }

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

    friend std::ostream& operator<<(std::ostream& os, const SillyJob& sj)
    { return os << sj.priority << ": " << sj.description; }
};

static bool by_priority(const SillyJob& a, const SillyJob& 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 SillyJob&, const SillyJob&);
        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 является довольно хорошим примером плохого дизайна, но имейте в виду, что это было только для демонстрационных целей:)

Answer 3

Нет.

Элемент упорядочения очереди с приоритетами не обязательно должен быть целым.

Да.

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

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

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

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

Answer 4

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