Indexed Priority Queue (UPDATED) | Data Structures

[@rico5146]

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]

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]

WilliamFiset Thank you william!

[@UdayTejaOriginal]

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

[@tkingless]

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

[@tuantranluuquoc2910]

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!

[@jimmychu0807]

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

[@mehmanismayilov9317]

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

[@PLAZMAKE]

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

[@jckimis]

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!

[@David-iq1kd]

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]

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?

[@sahilanower9189]

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

[@erikjohnson9112]

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]

[@carnaqe1154]

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?

[@rachitsingh8040]

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]

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

[@timmmmmmmmmmmmmmmmmmmmmmmm]

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)

[@andreytamelo1183]

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]

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!

[@Aashishkumar-dg4op]

Please upload the videos related to centroid Decompositon.

[@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.

[@mikemihay]

Thank you!

[@Justicewarrior795]

James has an arrow in his leg. Loool

[@Spine223]

blud just saved me

[@tumblerwater4361]

What a dark example William exemplary video anyways.

[@enyinnaukattah2083]

Poor Akarsh

[@thallium54]

wow i'm early

[@ahmadbodayr7203]

READ ABOUT ISLAM WILLIAM ❤