Приоритетные очереди в GO - PullRequest
Новая
       17

Приоритетные очереди в GO

0 голосов
/ 21 февраля 2019

Может кто-нибудь объяснить мне эту вещь: я хочу реализовать приоритетную очередь в GO (реализация интерфейса получена из ссылка , но для самого низкого)

Мой код: 

pq := make(PriorityQueue, 0)

pq.Push(&Item{value: 0, priority: 0})

heap.Init(&pq)

fmt.Println(heap.Pop(&pq).(*Item))

item := &Item{value: 1, priority: 10}
pq.Push(item)
item = &Item{value: 2, priority: 20}
pq.Push(item)
item = &Item{value: 3, priority: 5}
pq.Push(item)

fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))

// Output:
&{0 0 -1}
&{1 10 -1}
&{3 5 -1}
&{2 20 -1}

Почему это не выводит: 

&{0 0 -1}
&{3 5 -1} 
...

Ответы [ 2 ]

0 голосов
/ 21 февраля 2019

Сначала обратите внимание, что вы сказали, что сначала вы ожидали самого низкого приоритета, но чем больше число, тем выше приоритет.Так должно быть 20, 10, 5, 0.

В документах:

Вынуть предметы;они приходят в порядке убывания приоритета.

Я просто взял ваши данные и поместил их в пример на странице документа (ссылка, которую вы указали).Проверьте это: play.golang.org / p / 7GyYgJ-HAwi

Основное отличие заключается в расположении heap.Init(&pq).

Редактировать: @ EliБендерский дал ответ, пока я печатал свой.

0 голосов
/ 21 февраля 2019

В способе реализации этой конкретной очереди приоритетов вы должны вызывать heap.Init после того, как вы поместили свои элементы в очередь, как показано в оригинальном примере. 

pq := make(PriorityQueue, 0)

pq.Push(&Item{value: "0", priority: 0, index: 0})
item := &Item{value: "1", priority: 10, index: 1}
pq.Push(item)
item = &Item{value: "2", priority: 20, index: 2}
pq.Push(item)
item = &Item{value: "3", priority: 5, index: 3}
pq.Push(item)

heap.Init(&pq)

fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))
fmt.Println(heap.Pop(&pq).(*Item))

Печатает элементы в порядке приоритета, как и ожидалось.

...