By far one of the best explanations I've seen. Thank you so much for this video, I just started covering trees along with heaps and this was very helpful, I don't know how you don't have more views/subscribers. I am now subscribed, I look forward to your videos! I just had one question, this might be a dumb one but I was wondering why did you use ">>" & "
@@mallew32 Yes, usually they are faster. However certain machine do have their math processor, which contains special instructions for multiplication/division.
It's such an awesome implementation. I implemented it by myself based on your video and I found for the shiftUp method, maybe we can optimize it a little bit by changing the logic as below: ``` void MaxHeap::_shiftUp(int i) { if (i > _size) return; if (i == 1) return; if (vect[p(i)] < vect[i]) { swap(vect[p(i)], vect[i]); _shiftUp(p(i)); } else return; } ``` By doing this, we don't need to always go to index 1.
@@CodingJesus Thanks for sharing. I am looking forward to your more posts such as LRU/LFU, red-black tree. It is very nice you also post hash table implementation.
there is a subtle off-by-one error in the r() and l() methods. Vector indices are always less by 1 than the actual index. So, l() should return i1 (to implement i*2 + 1 and i/2 respectively)
I think I did not understand or there is a problem in the code - shiftDown should have if (i >= _size), and not if(i > _size), and also, why didnt you just say in shiftUp that it should stop after it didnt replace the item?
i have a question what if we want to heap sort then we can delete all element and print the vector ,but what if we want to correct it again 40 30 20 15 10 , it will be 20 30 40 15 10 .which is not right ,so how we can fix that ?!
it is giving me error on 12 line where vector vect = {-1}; [Error] converting to 'std::vector' from initializer list would use explicit constructor 'std::vector::vector(std::vector::size_type, const value_type&, const allocator_type&) [with _Tp = int; _Alloc = std::allocator; std::vector::size_type = long long unsigned int;
6:50 it is not the "smallest element", but the last added which gets swapped. - Take your time to make things clear. For me, you rushed way to fast through this.
@@sarthakbhatia1728 It's C++11 syntax, brace initialization. It initializes the declared variable to it's default value (in this case 0). Without it, it would contain a junk value.
@@sarthakbhatia1728 If a vector has 10 elements, you cannot index into its 11th element. So because I can't index into the 11th element, I add a place holder (0), and both increment the size of the vector, and change the placeholders value to the value I'd like it to be.
#include using namespace std; class max_heap{ private: vector arr = {-1}; int _size{}; int p(int indx) {return indx>>1;}; int l(int indx) {return indx_size) return;
int largest = indx; if (l(indx)InsertHeap(34); pq->InsertHeap(41); pq->InsertHeap(5); cout MaxHeap() ExtractHeap(); cout MaxHeap() ExtractHeap(); cout MaxHeap()
Hey I made a pastebin from your code. For some reason I just get correct from the isEmpty, but nothing else from the vectors work. I can link the pastebin here or the code, whatever works pastebin: pastebin.com/4X7BTLYz
This is the best implementation of a priority queue ever. Thank you so much
Man, Thank You for taking the time to explain what my Uni lecturers would not.
By far one of the best explanations I've seen. Thank you so much for this video, I just started covering trees along with heaps and this was very helpful, I don't know how you don't have more views/subscribers. I am now subscribed, I look forward to your videos! I just had one question, this might be a dumb one but I was wondering why did you use ">>" & "
Because bitshifting a number to the left multiplied it by 2, and bitshifting to the right divides it by 2.
Thanks for your support!
This is a great question. To follow up on it, @Coding Jesus, is it faster in c++ to bitshift than to multiply/divide?
@@mallew32 Yes, usually they are faster. However certain machine do have their math processor, which contains special instructions for multiplication/division.
It's such an awesome implementation. I implemented it by myself based on your video and I found for the shiftUp method, maybe we can optimize it a little bit by changing the logic as below:
```
void MaxHeap::_shiftUp(int i) {
if (i > _size) return;
if (i == 1) return;
if (vect[p(i)] < vect[i]) {
swap(vect[p(i)], vect[i]);
_shiftUp(p(i));
}
else return;
}
```
By doing this, we don't need to always go to index 1.
Thanks for the kind words.
@@CodingJesus Thanks for the nice post.
yeah, i was about to comment the same thing but as a question, as i am not very familiar with these things
I had a doubt in shifDown function when reading online article, but after watching your video doubt is cleared thanks.
Let's ignore the explanation and assume it's a muted video; he can write good readable code.
Good video.
Damn bro , this is quality content holy shit
This is awesome. 1 based indexing is exactly what I am looking for. Thanks.
Cheers! Thanks for subscribing.
@@CodingJesus Thanks for sharing. I am looking forward to your more posts such as LRU/LFU, red-black tree. It is very nice you also post hash table implementation.
@@jimmyshenmusic Yeah I'm going to make a series on data structures. Thanks for those suggestions.
@@CodingJesus That's great. I am preparing coding interviews and I found the LRU is very frequently asked.
One of the best explanations I have seen, thanks!
Thanks!! It was so clear. Hope you continue making such great videos.
Thank you, I will
Thank you man, in my laungage "possałbym bym ci jajca za to".
Much appreciated. Very good explanation.
cheers
Why the semicolons after the closing curly brace on method bodies?
there is a subtle off-by-one error in the r() and l() methods. Vector indices are always less by 1 than the actual index. So, l() should return i1 (to implement i*2 + 1 and i/2 respectively)
nice to see such a clean code ! the 1 base idx was very clever idea
Glad you like it!
Damn bro, 🔥 explanation. Instantly hit that subscribe button. This is good shit homie, quality content.
Coding Jesus you are the man! Great explanation thank you. I hope to see more videos from you
You can see more if you subscribe. :D
What a great explanation bro, nailed it.
Thanks
I think I did not understand or there is a problem in the code - shiftDown should have if (i >= _size), and not if(i > _size), and also, why didnt you just say in shiftUp that it should stop after it didnt replace the item?
How can I get the code? Thanks
Nice work man, it was really helpful... !!
If you can, next video, implement graphs and implement BFS and DFS... !!
Is there any specific reason that the first index in the heap needs to be a garbage value? Can't we just make index 0 the max instead of 1?
0 times any number is always 0.
really good explanation
Great explanation. Keep it up
nice video, great explanation
I dont code so i have no idea whats going on but what would be the purpose of the implementation of this code?
Mix and max heaps are very fast to sort and the lowest value is always guaranteed to be the root node which again is very quick to access.
Can I get code?
I think using vect.pop_back()(after swap) and size- - would be better since this will release the memory
good advice
Great video, it was a real help, thanks man.
i have a question what if we want to heap sort then we can delete all element and print the vector ,but what if
we want to correct it again 40 30 20 15 10 , it will be 20 30 40 15 10 .which is not right ,so how we can fix that ?!
I don't understand your question
it is giving me error on 12 line where vector vect = {-1};
[Error] converting to 'std::vector' from initializer list would use explicit constructor 'std::vector::vector(std::vector::size_type, const value_type&, const allocator_type&) [with _Tp = int; _Alloc = std::allocator; std::vector::size_type = long long unsigned int;
Works just fine, the problem is somewhere else in your code.
godbolt.org/z/b187f8
hey man, just thought i'd say i wouldn't recommend putting stuff like i
6:50 it is not the "smallest element", but the last added which gets swapped. - Take your time to make things clear. For me, you rushed way to fast through this.
Please Give me all code
what does _size{} mean
?
Also,thanks :)
_size = 0
@@CodingJesus is it some C++ syntax or does it convey something. Like , what are those extra braces for?
and also please explain this if condition in insert function
@@sarthakbhatia1728 It's C++11 syntax, brace initialization. It initializes the declared variable to it's default value (in this case 0). Without it, it would contain a junk value.
@@sarthakbhatia1728 If a vector has 10 elements, you cannot index into its 11th element. So because I can't index into the 11th element, I add a place holder (0), and both increment the size of the vector, and change the placeholders value to the value I'd like it to be.
this is damn good explanation, thnku so much
thx man!
No problem!
Thanks
Ur keyboard making too much noise
😅
do sorts please
#include
using namespace std;
class max_heap{
private:
vector arr = {-1};
int _size{};
int p(int indx) {return indx>>1;};
int l(int indx) {return indx_size)
return;
int largest = indx;
if (l(indx)InsertHeap(34);
pq->InsertHeap(41);
pq->InsertHeap(5);
cout MaxHeap() ExtractHeap();
cout MaxHeap() ExtractHeap();
cout MaxHeap()
Same code but it is not working @Coding Jesus
Hey I made a pastebin from your code. For some reason I just get correct from the isEmpty, but nothing else from the vectors work.
I can link the pastebin here or the code, whatever works
pastebin: pastebin.com/4X7BTLYz
//heap
#include
#include
using namespace std;
class MaxHeap
{
private:
int _size{};
vector vect = { -1 };
int p(int i) {
return(i >> 1);
};
int l(int i)
{
return i vect[p(i)])
swap(vect[p(i)], vect[i]);
shiftUp(_size);
return;
}
void shiftDown(int i)
{
if (i > _size) return;
int swapId = i;// want to track comparisons
if (l(i) isEmpty())
cout insertItem(120);
PriorQ->insertItem(34);
PriorQ->insertItem(41);
PriorQ->insertItem(5);
cout getMax() extractMax();
cout getMax() isEmpty())
{
cout
thank you so much!!