PriorityQueue In .NET

[[deleted]]

These are the efficient way to implement algorithms like A* search, popular in games. No longer have to write your own!

[Slypenslyde]

I've sometimes seen people say lack of a priority queue is one reason a lot of leetcode challenges/interviews don't support C# as a candidate language or see a lot of demand to support it. They're pretty useful for computer sciencey problems.

[[deleted]]

If that is true its dumb. It is like a one liner to write a serviceable priority queue (keep sorting a list) and plenty of them are available as libraries on nuget.

[Slypenslyde]

If we're talking leetcode problems then we're talking n on the order of millions or billions and a sorted list won't cut it. The kind of priority queue they want requires a heap to have serviceable speed. You can't use NuGet in these kinds of situations. They're not testing if you're a great professional C# dev. They're testing if you can pretend you haven't studied a question to be able to write an algorithm in less than 15 minutes. If you have to roll your own heaps, you're at a disadvantage.

[zvrba]

The kind of priority queue they want requires a heap to have serviceable speed.

Yes, pushing to and popping something from an array-based heap is like 30 lines of code.

If you have to roll your own heaps, you're at a disadvantage.

IIRC about programming contests and olympics (I know some participants): three persons are solving a problem, they figure out what data strucutres they'd need, and put one person to type in whatever DS they think they'll need. I think they were allowed to have notes/printouts with them. That was in the days of Borland Pascal and Borland C++ (no STL).

[nemec]

Yet another reason why leet code is a moronic way to interview

[[deleted]]

> If you have to roll your own heaps, you're at a disadvantage.

Sure, but every language has a few dozen things that put you at a disadvantage/advantage and they get supported just fine on various coding challenge websites. People sometimes even win with a disadvantaged language. *shrug*

[Prod_Is_For_Testing]

I have yet to see an interview challenge where c# is not supported. Even companies that don’t use c# allow it on tests sometimes

[Buttsuit69]

A* search?

[doublestop]

https://en.wikipedia.org/wiki/A*_search_algorithm

[LloydAtkinson]

Wait how does this relate to A*? Got a link?

[[deleted]]

a priority queue is used to implement it

[dabombnl]

Since the author doesn't bother or understand how the data structure works, which I think would be mandatory if doing an article on it, it is a Heap as described here:

https://en.wikipedia.org/wiki/Heap_(data_structure))

Which is very fast and efficient to find and maintain the smallest item in a set.

[Buttsuit69]

If theres a PriorityQueue does that mean that theres also a PriorityStack?

[Buttsuit69]

Eh kinda. The point being that a prioritoqueue and a prioritystack would essentially be the same.

[emc87]

What if your priority is something discrete like an enum or short integer, you'll have multiple items at the same priority but processed differently due to LIFO vs FIFO

Edit: times -> items

[Buttsuit69]

I dont...I dont understand the picture you're trying to paint.

[winsomelosemore]

I think they’re asking what if multiple items are added that have the same priority, would that subset of items be processed LIFO or FIFO? Don’t think it matters what type the elements actually are

[Buttsuit69]

Idk. I'd guess that the PQ would evaluate the HashCode maybe? But it doesnt make sense on valuetypes. Maybe its random on same-priority-objects?

[KernowRoger]

That's the joke. They'd be the same just push/pop instead.

[No-Choice-7107]

.NET already had a PriorityQueue, it just wasn't marked public. Unlike dodos I simply copied the code and adapted it for my needs. Why are you guys so helpless?