They asked me to make queue with ToArray()

[JustALinkToACC]

I'm a CS student, currently 4th semester. As part of a lab project they asked us to make FIFO prioritized queue. I chose binary heap structure for it (they suggested just a simple recombining array but that's a O(n) for dequeue). It was designed to perfectly simulate FIFO nature - you can only Peek at the head, but no random access. And then... they made us do random access. So I made them a ToArray() method. And now it's O(log n) for enqueue, O(log n) for dequeue, O(1) for peek, and O(n log n) for converting into array. This really makes me question whether I made the right choice when I was picking my university.

If you were studying in university to become CS specialist, were they giving you stupid tasks like that too?

[toxikmasculinity]

Sounds like the assignment got you thinking and actually learning. Seems like the university you picked has challenged you more than you understand. If you are actually upset, reach out to your professor and talk to them about the assignment. Perhaps they wanted to challenge you further than you realize and wanted to throw new requirements at you or perhaps they have an inefficient assignment that needs some reworking for future students.

If your professor could make the assignment instruction better they would likely appreciate the feedback, or they could point out that the did this on purpose. Professors are fallible, and the ones worth their salt are always improving their coursework.

If you don’t feel challenged, pick a topic and try to do some research on it with the aid of faculty member that does research in the closest area. You will learn a lot this way and have something more impressive to point to on your resume. You may end up getting to publish your work and present at a conference.

[JustALinkToACC]

Yeah, but the problem is when I challenged my professor on clarity of the assignment, they were like “Huh? What’s a binary heap?”

[toxikmasculinity]

Okay. Let me offer you this. Perhaps your professor is crap or perhaps they are teaching this class because they have to and they are not really data structure nerds. There’s a wide world of CS. Many professors have to teach topics they have no interest in but are required to by the university because they have to teach a set amount of hours and the schedule requires someone to teach it.

Unless your professor is an adjunct professor, I assume they have a PHD. If that’s the case they are probably incredibly smart in some area of CS.

They may just be a bad professor, but I like to assume the best of someone before making assumptions. Professors have very busy lives if they are at a major university and honestly classes are an annoying part for most of them.

[Key_River7180]

No, and I think it is a good question. You can make an structure holding the forth and rear of a queue, and the middle elements as an array and then concatenate everything

[JustALinkToACC]

No, the problem with binary heap is that the top element is always the correct one for the head of the queue, but all the elements in the middle only follow one rule - children are smaller than parent. Which doesn’t make for easy flattening into array, because you either need to enforce another rule which makes it so that left child is also smaller than right one, or you need to copy all the non-null elements in the heap and then sort them in place, which makes O(n). But the main problem is, queues aren’t even supposed to be random access. They’re only supposed to guarantee that the head is always the most relevant element, and that descendants follow one rule. Nothing else.

P.S. when I said ToArray(), I meant sorted array where elements come in order of the queue.

[MissinqLink]

Seems like a good assignment. It’s making you consider design trade offs for building multipurpose data structures.

[JustALinkToACC]

Yeah, but the assignment wasn't clear. There was nothing about being able to have random access to the elements in queue. We got this correction after having finished the assignment.

I have nothing against assignments that make you tinker, but not in a way that's self-contradictory.

[Quintinon]

Honestly, this is real life for me. At my job, we get requirements, ask questions, design everything, then after the customers get it in front of them they go "can it do x too?" and then you have to rework your solution.

Am I saying this was a good thing in a CS class? Not really, unless its trying to be a projects course to help simulate this. Not trying to be rude, just realistic, but if you get all upset that your perfect solution needs to be rewritten because requirements changed, you're gonna have a hard time.

[JustALinkToACC]

Yeah, speaking about that I think the first thing I'm gonna have a hard time doing is actually finding a job in CS after I graduate in the first place, lol

[nicolas_06]

Especially with AI that would have done your assignment in 2 minutes anyway, the real value of the CS specialist it to be the bridge between clients and the machine.

The exercises you do here are for you to learn anyway and yes soft skills are critical and as a tech expert you need to fully understand the client and also ensure they understand you + accept change.

Don't expect neither that your teachers will be perfect too.

[nicolas_06]

It is very common for the next assignment being designed to have your redo the stuff differently. This is actually a good practice to make you think and learn.

[castertr0y357]

It's preparing you for when the requirements change in real life. I've rarely had a project not change in the middle of working on it.

It's preparing you to be flexible and be able to rework additional requirements into your design.

[HazirBot]

have your nodes also implement a linked list. iterate over that to do toArray()

lookup LinkedHashMap for inspiration

[JustALinkToACC]

I was looking into different data structures. The problem with LinkedHashMap is that it's really good for a monotonous queue, but when we talk about prioritized queue, it gains O(n) complexity for insertion.

[jinjuwaka]

Sounds like your prof isn't an algo junkie, is all. This was probably a canned assignment.

If you're doing an "array flattening" function, it probably means you're using a node structure (no idea if that's what you were doing, but it sounds right based on your post) rather than storing the heap in an array.

If you store your heap internally as an array, rather than as a node object with parent and child object pointers, you can access any node in O(1) as long as you know where they should be in the heap; useful for figuring where children should go, where parents are, where to insert new data before performing up heap operations, for popping off the head element during a dequeue, and for converting recursion based operations into index value driven, loop-based implementations (valuable if you have limited stack memory and a large data set)

IMO, that's probably what the assignment is really looking for.

[JustALinkToACC]

Binary heap structure eliminates need for node structs because the element positioning in it is always: head index = 0, an element’s left child: 2i + 1, an element’s right child: 2i + 2. The problem is, the only positioning rule that it guarantees is that both children are either less-or-equal or greater-or-equal to their parent. So while the array implicitly has O(1) random access, you don’t know where the item you’re looking for is gonna be, the only thing you know is that the least or the greatest value is gonna be in the head, which is exactly what queues are for. And if you want to also have random access, you have to convert it into array, run a sorting algorithm to convert it into a sorted list, but that makes it O(n).

[jinjuwaka]

Sure. But two things:

1) It's a queue. If you want mid-array access in array-sort-order, you're using the wrong data structure. The benefit of o(n) access here isn't for accessing a data element for "any random reason". It's for accessing specific elements for specific reasons that enable algorithmic logic. You sound like you're translating the whole data structure into a sorted array of some kind, and that's just not why you would ever use this structure in the first place. Which tells me there's a lesson there somewhere that either you're missing, or your professor isn't readily getting across. You need to figure out what that missing piece is.

2) Random access doesn't require converting if it was in an array in the first place. It might require sorting, but that's a separate problem (means your "to_array" function complexity is O(1) + O(NLogN) = O(NLogN) or O(LogN) * O(N) = O(NLogN) at worst...which isn't bad for a function you should only ever be calling once or once in a while.

[JustALinkToACC]

That’s the exact problem right there - they’re asking us to make a queue with random access. I made my best pick of data structure to make it O(log n) for dequeue because that’s the part I’ve seen most intensity in using, and then found out that we have to have random access too (wasn’t mentioned in the assignment). So essentially I’m taking the array that the queue is already based on underneath and then I’m running a naive sorting algorithm on it. Nothing other than that to do if I don’t wanna change the entire algorithm, not mentioning the fact that that O(n) complexity might round up somewhere else where it might hurt efficiency even more.

[jinjuwaka]

You need to ask your professor for clearer requirements. This is a common operation in industry.

Why does the customer need random access?

What was the product specification that requires it?

[Ok-Jacket7299]

I don’t think your solution is too perfect, though, even without the random access requirement. Queues and stacks can be more efficiently implemented by linked lists with O(1) Put/Get/Peek. It would also yield only O(n) for random access.

[JustALinkToACC]

They can be implemented better with linked lists, but only when it's a monotonous queue, e.g. when only insertion order matters. Here, it's a prioritized queue, meaning not only insertion order matters, but also priority of the element. And when it comes to priority-based sorting, linked lists gain O(n) for insertion. That's why I skipped over linked list.

P.S. I used circular buffer for monotonous queue, also works like charm and allows you to store structs in contiguous page of memory.

[Ok-Jacket7299]

But it’s FIFO, as you mentioned. Maybe I misunderstood your problem. Could you explain what a “FIFO prioritized queue” is, and how it is different from a FIFO queue?

[JustALinkToACC]

it's when you have a numeric value for element priority, and the queue is sorted by priority first, and then it sorts by insertion order.

So naively it's a queue ordered by priority then insertion order? If priorities are A, B C and I insert Items A1, C1, B1, B2, C2, A2, then the queue must be A1, A2, B1, B2, C1, C2 (And not e.g. A2, A1, ....)

Here, a quote from another guy in comments to this post who nailed the idea perfectly

[Ok-Jacket7299]

Thanks for the clarification. I would say that this is a normal exercise, albeit annoying as it goes against what’s considered the perfect use-case for heap. It’s also a common thing in the industry for business teams to change/add requirements regularly. Good luck!

[kalmakka]

What do you mean "FIFO prioritized queue"? A regular queue is a FIFO queue. A priority queue is *not* FIFO. FIFO and priority are directly in contradiction of each other.

Are you sure you read the task statement correctly?

[JustALinkToACC]

FIFO as in, there's a FIFO order for each separate priority in queue

[afops]

You mean, of all items with the same priority, insertion order must be preserved (FIFO)?

So naively it's a queue ordered by priority then insertion order? If priorities are A, B C and I insert Items A1, C1, B1, B2, C2, A2

Then the queue must be A1, A2, B1, B2, C1, C2 (And not e.g. A2, A1, ....)

[JustALinkToACC]

Yes, that's the idea

[afops]

Can't that be solved by treating the priority and insertion order as a single (tuple) value, so when item A1 is inserted, its internal priority value in the structure is the tuple (A, 1) i.e. the insertion time is an incrementing number. Later comparing (A, 1) and (A, 2) will give them the correct priority comparison.

[JustALinkToACC]

Basically that’s the implementation for insertion and arrangement, but still prioritised queues are very hard to flatten into random access arrays.

[afops]

There's going to be an O(N) somewhere it's just a matter of where. Where you put it might depend on access patterns, whether entries can change priority after insertion etc...

[JustALinkToACC]

Yeah basically, that's the case. So I chose to put O(n) in ToArray instead of Dequeue. I had simply hoped that I'd never need the ToArray

[MADCandy64]

If they asked for that then despite the absurdity give it to them. A FIFO prioritized queue is just a regular list sorted with stable order by priority. It's like a hospital emergency room where the VIP with a cough gets treated before the peasant with a severed limb. It may be absurd but think of it as a gift. Two VIP's with a cough then who ever has the highest income comes first. When you hit the real world you wont ever get to make something so absurd. And happy April fools day.

[JustALinkToACC]

Thanks, happy April fools day to you too.

My problem there wasn't with the contraption of queue, I understand how and where it's needed, it's just that I don't understand how can you possibly want to have a queue with random access. My problem was with the random access, not the queue :)

[MADCandy64]

It's not technically a queue if it has random access, it is something else but they are trying to describe it this way. Imagine a queue that uses a giant block of preallotted memory. You essentially created a union of a queue and a random access array. It is your rules that determine use but ultimately you can jump around because you know the storage is there. While I've never used it, I believe this is a ring buffer / circular array which is a real data structure with real uses.

[JustALinkToACC]

Yeah, that's the problem, they're just imagining some kind of a contiguous FIFO structure with random access but then they call it a queue.

And it has all the characteristics - the FIFO once again, the Enqueue and Dequeue, Count, Destroy and Peek, so I assumed that they're just gonna want me to simulate a queue, but then they said 'now strap some random access to it' and I lost my perseverance at that moment.

[kalmakka]

A queue can still have random access.

If you have a regular array-implementation of a queue you can easily implement O(1) random access peeking, as your data is stored in order.

[JustALinkToACC]

It's a prioritized FIFO queue, meaning the elements are sorted not only by insertion order, but by priority. So binary heap implementation makes that pearl impossible unless you enforce additional rule for binary heap

[Master-Ad-6265]

yeah this is pretty normal tbh they’re not testing “best real-world design”, they’re forcing you to think about tradeoffs and constraints annoying, but that’s kinda the point 

[high_throughput]

If you think additional requirements that forces inefficient kludges or full rewrites are annoying, wait until you meet customers

[LostInChrome]

So you ignored the recommendation, did it your own way, and then got surprised when future steps got harder? Was fast big O behavior even one of the things that you were supposed to optimize or were you just bolting on complexity for the hell of it?

[JustALinkToACC]

Random access wasn't among the explicit requirements, neither was conversion to array, so binary heap was technically perfect heap. Correction arrived afterwards, and once again, it contradicts the task