Supposedly this is a condition for constructing min heaps. Perhaps the reasoning could be backed by looking at the search technique used to search a particular node in this tree. Breadth First Search (BFS) uses this traversal mechanism to visit each node level by level and placing a node to the left saves time.
Hi william, i have query regarding with hashtable approach to reduce time complexity for removal, 1. wont the constant updation of hashtable involve additional time complexity 2. when array size grows bigger than capacity, elements of hashtable needs to flushed and repopulated, will it not be complex. 3. Further, to take care concurrency will this approach add time in lock aquire duration? As i saw java implementation of priorityBlockingQueue and remove method still is O(n) and hence asking above questions for clear use cases
1) First we need to examine when we would need to update the hash table. The answer to this is for every swap that has occurred. How many swaps do we do? O(log(n)). So whats occurring here is the removal process takes log(n) because of the swaps we're performing and we'd only need to update 2log(n) which gets you O(log(n)). So it does not increase the time complexity. 2) Are you referring to using an array as the value of the hash table? If thats the case then you should probably use a more dynamic data structure such as a doubly linked list. This will allow you to insert without having to worry about a "capacity" and only the systems memory limits - which would require us to dive into scalability and I believe thats a bit outside the scope of this video. 3) Hmmm. Trying to implement this algorithm with effective multithreading would definitely be either extremely difficult or impossible. I would love to see if you've actually been able to implement this.
Correct! And as explained earlier on in the video if two child nodes have the same value you can arbitrarily pick which one to swap. I usually just default to the left node when this happens.
this is really late but for anyone interested: he chooses the lesser of the two children (in this case 5) because if he chose the greater of the two children it would lead to a violation of the order property. This is also why as he swam downward, he chose to swap 15 and 8, as if he had chosen 13, it would've violated the order property as well.
In the hospital example earlier in the playlist, if you have someone drop out of the hospital queue, that represents a specific person even if that person's priority happens to match that of another person. I'm sure I'm misunderstanding something as this video makes it sound like during a removal, as long as you remove something of the same priority level it doesn't matter which one, but for the sake of removing the correct / specific person from the queue would you need to map the index tree to the person's ID instead of to a priority number or something? Or do you still have to do a lookup scan in this case?
I am still confused when to bubble up and bubble down when deleting. I mean I got the understanding visually but unable to think in term of logical implementation
If the numbers represent a priority, I see how if you know a priority value for an item, you can add it and it will fall to the correct place in the binary tree. What if your priorities are relative? So you aren't on some priority scale like 1-10, but you want to say "prioritize this activity Z between activity A and B?" Is this a different data structure entirely?
In priority queue max binary heap deletion operation if we want to delete root node 6 and the child node of left and right is 5 then what node should i delete left or right
When doing the poll() or remove(), when we swap with the last element, do we need to do linear search to find the last element. How does the heap knows where and which is the last element?
You have a variable named size, so you can easily get to the end of the array. For example, size = 5 and arr[size - 1] = size[4] would be the last element so it only takes a constant time to swap the elements.
It's also a lower-level dynamic vs. static array issue. With a dynamic array (like Python's list []), you usually grab the last element with the pop() function. That automatically shrinks the list as well. So with a dynamic array you never worry about it. If you have a fixed-sized array, then like Tianxin mentioned you need a size variable that's updated as the heap grows/shrink. You also need to handle capacity increase (i.e. doubling for instance) when the heap is full.
in the Remove(12), what about searching for the the 12 using binary search as the array is sorted in some way so we can search in order of logn instead of linear
5:18 Shouldn't be the time complexity for removal of any element be O(n +log(n)), as along with searching we are also bubbling up or down?
n is the greater factor so O(n+log(n))=O(n)
I think that log(n) is non dominant term so it doesn't come in the complexity analysis in this case
2:00 Is there as a reason the left node is selected as the tiebreaker when bubbling down or is it arbitrary?
Supposedly this is a condition for constructing min heaps. Perhaps the reasoning could be backed by looking at the search technique used to search a particular node in this tree. Breadth First Search (BFS) uses this traversal mechanism to visit each node level by level and placing a node to the left saves time.
Same question! What about selecting the right node?
You're a lifesaver.
2:10 What happens if the element is bubbled down to a position that causes the tree to be in violation of the tree complete property?
The tree will always maintain its intrinsic property for all the elements recursively , this leaves no room for error.
Hi william, i have query regarding with hashtable approach to reduce time complexity for removal,
1. wont the constant updation of hashtable involve additional time complexity
2. when array size grows bigger than capacity, elements of hashtable needs to flushed and repopulated, will it not be complex.
3. Further, to take care concurrency will this approach add time in lock aquire duration?
As i saw java implementation of priorityBlockingQueue and remove method still is O(n) and hence asking above questions for clear use cases
1) First we need to examine when we would need to update the hash table. The answer to this is for every swap that has occurred. How many swaps do we do? O(log(n)). So whats occurring here is the removal process takes log(n) because of the swaps we're performing and we'd only need to update 2log(n) which gets you O(log(n)). So it does not increase the time complexity.
2) Are you referring to using an array as the value of the hash table? If thats the case then you should probably use a more dynamic data structure such as a doubly linked list. This will allow you to insert without having to worry about a "capacity" and only the systems memory limits - which would require us to dive into scalability and I believe thats a bit outside the scope of this video.
3) Hmmm. Trying to implement this algorithm with effective multithreading would definitely be either extremely difficult or impossible. I would love to see if you've actually been able to implement this.
at 4:19 how do u decide bubbling down 15 between 5 and 6 ?
Because we're constructing a min heap you would pick the smallest one to satisfy the heap invariant.
WilliamFiset so we should choose the smallest child node ! Thanks :D
Correct! And as explained earlier on in the video if two child nodes have the same value you can arbitrarily pick which one to swap. I usually just default to the left node when this happens.
WilliamFiset thanks a lot !
this is really late but for anyone interested: he chooses the lesser of the two children (in this case 5) because if he chose the greater of the two children it would lead to a violation of the order property. This is also why as he swam downward, he chose to swap 15 and 8, as if he had chosen 13, it would've violated the order property as well.
In the hospital example earlier in the playlist, if you have someone drop out of the hospital queue, that represents a specific person even if that person's priority happens to match that of another person. I'm sure I'm misunderstanding something as this video makes it sound like during a removal, as long as you remove something of the same priority level it doesn't matter which one, but for the sake of removing the correct / specific person from the queue would you need to map the index tree to the person's ID instead of to a priority number or something? Or do you still have to do a lookup scan in this case?
I am still confused when to bubble up and bubble down when deleting. I mean I got the understanding visually but unable to think in term of logical implementation
If the numbers represent a priority, I see how if you know a priority value for an item, you can add it and it will fall to the correct place in the binary tree. What if your priorities are relative? So you aren't on some priority scale like 1-10, but you want to say "prioritize this activity Z between activity A and B?" Is this a different data structure entirely?
I have a concern. If we arbitrarily remove elements from a priority queue, is it still a priority queue?
thanks. adding a comment for YT's algo.
In priority queue max binary heap deletion operation if we want to delete root node 6 and the child node of left and right is 5 then what node should i delete left or right
always outstanding....great content
this is great, thank you 🌟
When doing the poll() or remove(), when we swap with the last element, do we need to do linear search to find the last element. How does the heap knows where and which is the last element?
You have a variable named size, so you can easily get to the end of the array. For example, size = 5 and arr[size - 1] = size[4] would be the last element so it only takes a constant time to swap the elements.
It's also a lower-level dynamic vs. static array issue. With a dynamic array (like Python's list []), you usually grab the last element with the pop() function. That automatically shrinks the list as well. So with a dynamic array you never worry about it. If you have a fixed-sized array, then like Tianxin mentioned you need a size variable that's updated as the heap grows/shrink. You also need to handle capacity increase (i.e. doubling for instance) when the heap is full.
thank you for the lecture. btw have anyone ever mentioned that u sound just like criticalMoist lol
Thank you very much
in the Remove(12), what about searching for the the 12 using binary search as the array is sorted in some way so we can search in order of logn instead of linear
The array that stores the tree is not sorted, so no binary search.
video title says priority queue, video shows binary heap..
hell yeah im the first viewer :D