Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
29 / 22 / 15
Регистрация: 31.03.2018
Сообщений: 398
1

Очередь с приоритетом

01.05.2019, 01:05. Просмотров 1426. Ответов 4

Доброй ночи!
Как создать очередь с приоритетом? Объясните пожалуйста.

И еще один вопросик: двоичная куча является очередью с приоритетом или это разные понятия?

P.S. Демонстрация кода не обязательна, но если возможна - очень-очень приветствуется
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.05.2019, 01:05
Ответы с готовыми решениями:

Очередь с приоритетом
Всем привет, есть задание (на картинке) Из него сделал все, но не пойму что требуется в последнем...

Очередь с приоритетом сделать многопоточной
Добрый день. Есть реализованная очередь с приоритетом. Реализованы операции вставки, извлечения и...

Сделать очередь с приоритетом, которая бы работала с классом Message<TPriority, TContent>
Добрый день. Пытаюсь вот понять одну штуку. У меня есть некий класс - сообщение: public class...

Очередь с приоритетом. Элементы с наивысшим приоритетом ставятся в начало очереди, с наименьшим – в конец
Здравствуйте! имеется задание: создать очередь с приоритетом (у каждого элемента свой приоритет)....

4
Эксперт .NET
14470 / 10915 / 2882
Регистрация: 17.09.2011
Сообщений: 18,432
01.05.2019, 09:42 2
Лучший ответ Сообщение было отмечено Iangyl как решение

Решение

Цитата Сообщение от Iangyl Посмотреть сообщение
Как создать очередь с приоритетом?
Ну учитывая вот это условие:
Цитата Сообщение от Iangyl Посмотреть сообщение
Демонстрация кода не обязательна
то все просто:
C#
1
2
3
4
public class PriorityQueue<TPriority, TItem> : IEnumerable<TItem>, IEnumerable<KeyValuePair<TPriority, TItem>>
{
   // Magic
}
Самая простая реализация "на коленке":
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class PriorityQueue<TPriority, TItem> : IEnumerable<TItem>, IEnumerable<KeyValuePair<TPriority, TItem>>
{
    private readonly SortedDictionary<TPriority, Queue<TItem>> _storage;
 
    public PriorityQueue() : this(Comparer<TPriority>.Default)
    {
 
    }
 
    public PriorityQueue(IComparer<TPriority> comparer)
    {
        _storage = new SortedDictionary<TPriority, Queue<TItem>>(comparer);
    }
 
    public int Count
    {
        get;
        private set;
    }
 
    public void Enqueue(TPriority priority, TItem item)
    {
        if (!_storage.TryGetValue(priority, out var queue))
            _storage[priority] = queue = new Queue<TItem>();
        queue.Enqueue(item);
 
        Count++;
    }
 
    public TItem Dequeue()
    {
        if (Count == 0)
            throw new InvalidOperationException("Queue is empty");
 
        var queue = _storage.First();
        var item = queue.Value.Dequeue();
        
        if (queue.Value.Count == 0)
            _storage.Remove(queue.Key);
 
        Count--;
        return item;
    }
 
    public IEnumerator<KeyValuePair<TPriority, TItem>> GetEnumerator()
    {
        var items = from pair in _storage
                    from item in pair.Value
                    select new KeyValuePair<TPriority, TItem>(pair.Key, item);
 
        return items.GetEnumerator();
    }
 
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 
    IEnumerator<TItem> IEnumerable<TItem>.GetEnumerator()
    {
        var items = _storage.SelectMany(pair => pair.Value);
        return items.GetEnumerator();
    }
}
Цитата Сообщение от Iangyl Посмотреть сообщение
двоичная куча является очередью с приоритетом или это разные понятия?
Понятия разные, но двоичная куча может использоваться как деталь реализации очереди с приоритетом.
2
29 / 22 / 15
Регистрация: 31.03.2018
Сообщений: 398
29.05.2019, 17:41  [ТС] 3
kolorotur, о все хотел спросить, да не знал как правильно поставить вопрос, как определяется приоритет для значения при его вставке в очередь?
0
Эксперт .NET
14470 / 10915 / 2882
Регистрация: 17.09.2011
Сообщений: 18,432
29.05.2019, 18:30 4
Цитата Сообщение от Iangyl Посмотреть сообщение
как определяется приоритет для значения при его вставке в очередь?
Приоритет — это аргумент, передаваемый в метод Enqueue для первого параметра (priority)
1
29 / 22 / 15
Регистрация: 31.03.2018
Сообщений: 398
29.05.2019, 20:10  [ТС] 5
Кстати, я справился более простым и примитивным способом, вот пожалуйста(вдруг кому нужно будет):
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class QueueP
    {
        private int[] array { get; set; }
        private int[] priority { get; set; }
        private int maxSize;
        public int currentSize { get; private set; }
 
        public QueueP(int length)
        {
            maxSize = length;
            array = new int[maxSize];
            priority = new int[maxSize];
            currentSize = 0;
        }
        public void Show()
        {
            for (int i = 0; i < currentSize; i++)
            {
                Console.WriteLine(array[i] + " - " + priority[i] + "\n\n");
            }
        }
        public void Clear()
        {
            currentSize = 0;
        }
        public bool IsEmpty()
        {
            return currentSize == 0;
        }
        public bool IsFull()
        {
            return currentSize == maxSize;
        }
        public int GetCount()
        {
            return currentSize;
        }
        public void Push(int element, int prior)
        {
            if (!IsFull())
            {
                array[currentSize] = element;
                priority[currentSize] = prior;
                currentSize++;
            }
        }
        public int Pop()
        {
            if (!IsEmpty())
            {
                int max_pri = priority[0];//priority element
                int max_priIndex = 0;//priority index
 
                //find more priority mean
                for (int i = 0; i < currentSize; i++)
                {
                    if ((max_pri % 10) < (priority[i] % 10))
                    {
                        max_pri = priority[i];
                        max_priIndex = i;
                    }
                }
                int temp1 = array[max_priIndex];
                int temp2 = priority[max_priIndex];
 
                for (int i = max_priIndex; i < currentSize - 1; i++)
                {
                    array[i] = array[i + 1];
                    priority[i] = priority[i + 1];
                }
                //reduce quantity
                currentSize--;
                //come back 
                return temp1;
            }
            else return -1;
        }
    }
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.05.2019, 20:10

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Очередь с приоритетом
Здравствуйте! Нужна ваша помощь! Не могу разобраться в чём проблема. Создаю очередь с...

Очередь с приоритетом
Вообщем есть задание найти и описать проблему : Given a priority queue with the following...

Очередь с приоритетом
Может кто нибудь простыми словами объяснить что это за структура данных - очередь с приоритетом? И...

Очередь с приоритетом
есть очередь #include &lt;iostream&gt; #include &lt;queue&gt; using namespace std; int main() { ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.