Indexed Priority Queue (UPDATED)

Indexed Priority Queue (UPDATED) | Data Structures

Рет қаралды 26,572

Күн бұрын

Пікірлер: 32

@rico5146 4 жыл бұрын

Always thank you for uploading gorgeous videos william! btw, i noticed that at 20:47, i think sz = sz -1 should be located before swap (i, sz) cuz sz-1 point the last node of the heap.

@WilliamFiset-videos 4 жыл бұрын

Oops, that's a small bug. I looked in the source code I wrote for the IPQ and the size is decremented before the swap: github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/datastructures/priorityqueue/MinIndexedDHeap.java#L124

@rico5146 4 жыл бұрын

WilliamFiset Thank you william!

@UdayTejaOriginal 4 жыл бұрын

I kept the following 3 handy to understand easily: 'val' : input is keyIndex, output is Value 'pm' : input is keyIndex, output is position 'im' : input is position, output is keyIndex

@tuantranluuquoc2910 2 жыл бұрын

Man, the explanation can't get any better!!! Your lecture is such a treat to me as a self-taught programmer (though I still go to uni but my uni sucks a**...). Keep up the good work!

@PLAZMAKE 4 жыл бұрын

I was literally watching the old video and just saw this one. What a coincidence!

@jckimis 4 жыл бұрын

Just FYI, if you need further information for Indexed PQ, please see "2.4 Priority Queues" in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. @William, it's a really awesome lecture!

@mehmanismayilov9317 3 жыл бұрын

That is awesome explanation of less known but useful Data Structure IPQ

@tkingless Жыл бұрын

Must thank for this, much better than somewhere else I read

@erikjohnson9112 4 жыл бұрын

OK, now code this all on the whiteboard while I tell you about my cat Mittens, and the cutest things she does. [session 1 of 6 for today's interviews]

@jimmychu0807 Жыл бұрын

Thank, great explanation! This video helps me solve a problem I faced currently!

@sahilanower9189 3 жыл бұрын

My mind is going out of my indices after watching this!

@David-iq1kd 8 ай бұрын

What is the best way to persist your indexed priority queue into and reconstitute it from a database? Would a graph database be better suited to this? Is there a strategy for only reacting to the differential of the indexed priority queue that's saved to a database so you don't need to pull the entire queue every time, so that you can be notified immediately when the priority queue is updated (or especially being able to listen for when specific instances have their priority updated - like you're waiting in line and need to know when your place changes, without having to poll the database?)

@liviur23 4 жыл бұрын

The meaning of key indices (aka. ki) seems to overlap with the other two entities: names and positions in the binary heap. A ki is a stable (does not change across heap operations) key for a value but the name is also a stable key for a value. A ki is used to index into an array but the position number can also index into an array. So why not just map the names (which I believe are the proper keys used by client code) to the positions and reduce the number of mappings needed?

@rachitsingh8040 4 жыл бұрын

Hi William, Can you confirm if the min heap formed with key and value pairs is correct? Based of my understanding, min heap before performing any IPQ operations should be this: 0- (ki=7,v=1), 1-(ki=6,v=2), 2-(ki=0,v=3), 3-(ki=11,v=4), 4-(ki=9,v=5), 5-(ki=8,v=6), 6-(ki=4,v=7), 7-(ki=5,v=9), 8-(ki=2,v=11), 9-(ki=1,v=15), 10-(ki=10,v=16), 11-(ki=3,v=17) I sorted it by value. The arrangement is different than what I see in the video. What am I missing in my understanding here?

@WilliamFiset-videos 4 жыл бұрын

Min heaps aren't unique, so it's possible to have different trees depending on insertion order and where nodes are placed. The only thing that really matters is that the heap invariant is satisfied, i.e smaller values before larger values

@alexandrep4913 Жыл бұрын

I think your inverse mapping in the example is wrong or maybe the vals and PM are? Like you say "which person (key) is being represented in the node at index position 3". You then point to node at position 3, which has the ki of 8 but the value is 17 even though the node is 6. Are the values maybe wrong? Edit, no, your Inverse mapping is wrong. They need to match the key indexes or the array index given. Otherwise everything is wrong. Edit2, I am wrong lmao. It looks like Inverse mapping is an entirely separate entity from the other two arrays and the key index.

@timmmmmmmmmmmmmmmmmmmmmmmm 3 жыл бұрын

Great video! What is the motivation for using this approach over hash table (aka hash map) to achieve O(logn) delete or decrease / priority value (for dijkstra)

@carnaqe1154 8 ай бұрын

why do we have to map between keys and heapindexes? can we not just map keys directly to heap indexes and omit the two arrays which are just for mapping?

@andreytamelo1183 4 жыл бұрын

What about 'remove by key' followed by 'insert by key' scenario?After the 'remove' we should have a hole in the 'key-to-index' table.. What should the behavior be? Re-index? If not, how do we figure out the next key index we want to assign? Keep a separate min heap of free indexes to assign?:)

@renetchi 3 жыл бұрын

I still don't understand why the im inverse map is pointing to different person with different value?

@alexandrep4913 Жыл бұрын

separate the IM (inverse mapping) from the other two structures and it would make alot more sense to you. Then the index of the IM is the node index and the index of the vals and pm is the key index. Hope that makes sense!