Pretty basic stuff, adding, deleting, searching and printing the tree. Delete is screwing me right now but everything else is fine
That's actually why I made the meme, having a reference to the nodes parent would make this so much easier
Ok so I figured it out. God I hate it but it works
I was trying to rotate the node out of the tree but that was causing a lot of weird problems, so instead I swapped the node's *value* down the tree till it is at a leaf node, and just unlink whatever node the value ends up at from it's parent (which I kept track of every time I descended down the tree). I wrote a separate method to target a node by its value so I don't have to go down from the root when deleting.
Because it's a random priority bst the actual node where the value sits doesn't matter, only the value of the node does.
Not my best work, but the bit died about four hours ago and it works.
TBH I dont understand any of this shit, but I have been working as a senior for sometime now.
I learned it once but havent used it in a while.
These things trigger my imposter syndrome
If you asked me to do an infix traversal of a binary tree I'd have to Google the algo. This stuff isn't practical or useful to know but it builds problem solving skills you need later in your career.
All that to say, no one remembers all this stuff a year out of college.
Infix isn't complicated once you define the problem. There isn't an algo to remember as long as you know how to traverse trees and what's the order of traversal.
Graph coloring, travelling salesman. These should be better googled if you are writing some code for work.
Been a senior for a long time now. Never once needed this stuff. You shouldn't feel like an imposter for not knowing something that never comes up in your domain.
These things are only useful if you start implementing your own algorithms from scratch in rendering, compression etc. Nobody does this except as an academic exercise
What you find boring and what others find boring likely differs. Doing tight algorithm optimization \*can\* be interesting but I usually find it annoying to do in the scheme of the larger problems I'm working with, which are usually in the fullstack range-- I need to create a backend API endpoint, create the right DB queries, and then get it to the frontend, and build good code to render it out. This is all backed by the work I do to make sure the system deploys on its target and is configured correctly.
Since I have to do \*\*all\*\* of that, I'm incentivized to find quicker ways of solving a problem rather than having the code itself run more quickly. Most of my stuff is not computationally bound anyway, but latency-bound. Occasionally I do need to optimize an endpoint, but it's rare, and I don't remember the last time I had to actually deal with some complex tree structure in the way described by the OP. Usually a bit of work leveraging hash maps/sets, better specified DB queries and deliberate loop phrasing is enough.
Most of the tight algorithm stuff is stable work that's in whatever data structure library I'm working with. No need to learn it-- happy to let someone else handle that so I can ship. I have spent some time learning it anyway just to explore but it still never comes up.
If you like doing this kind of work, good for you, please do! We need people doing that and getting senior at it. That kind of drilled down focus is what produces the libraries that people like me use for the problems people like me find interesting. It's a big field out there. :)
I sidestepped all the comp-sci bullshit by doing a physics degree and I'm doing just fine. Not once have I felt the lacked "theory" actually impeded me, but then again I just write webapps rather than anything that cares about efficiency or speed
Welcome to recursive algorithms!
A heap is also a fractal. Each node is also a heap, and so you shouldn't need to refer to your parent to figure out the answer to your problem. Each node, each heap, in the heap reports its answer to its parent, and the parent then decides what to do based on the answers it receives.
When deleting nodes, you might think "well then I need to rebuild this whole branch." Correct, you do. The easiest way to rebalance is often to just build it again from scratch. So just have a recursive algorithm build a list of all nodes underneath the one you're deleting, build a new heap from those nodes, and tack it onto the existing structure.
Is it inefficient? Not really. Rejiggering pointer connections is cheap, and so is the math involved in the comparisons unless you have a complex data type with a difficult value to figure out. At that point, you'd need to perhaps having this comparison value be calculated upon creation of the element rather than at comparison time. It depends on your use-cases.
Addendum: This is true for heaps and other simple data structures.
Things like red-black binary search trees do have more optimized algorithms for rebalancing, but you'll learn about those when you get to them. They're not applicable here.
>When deleting nodes, you might think "well then I need to rebuild this whole branch." Correct, you do. The easiest way to rebalance is often to just build it again from scratch.
Yup. Had many troubles in Uni trying to program this same project because the rotating and balancing *had* to be done in-place
I mean, it IS the best work, as it's really the only way you can remove a random element from a heap. Moreover, it's exactly the same algo as the one for removing the top element since the subheap is also a heap, the only difference is to restore the link of the subheap's parent. It's easier if you use an array, but the idea is still the same - you sift the element through the heap swapping it with it's bigger priority child until it's gone.
The problem is not to remove an element, but to find it, which is not possible to do efficiently unless you use an additional lookup data structure.
Before I was trying to move the entire node, with this I'm only moving the node's values. The tree stricture stays exactly where it is. Makes it so much easier to use that algorithm without managing child positions and rotations and whatnot
I have no idea what you are doing with pointers. A max can be made with an array without any pointers. Only a tiny bit complex but if you already know how to make functions then it's not that complex.
Dude.
What you wrote sounds very wrong.
A heap is implemented on a variable length array.
No rotations are needed, only "bubbling".
And certainly no linking / unlinking of nodes.
I bet your professors want you to learn to implement a heap the proper way, not the wasteful way. If you need help, hit me up I'm good at this shit.
What’s wrong with storing a reference to the parent and then setting the parent’s next pointer to the current node’s next pointer? If you don’t have a parent pointer the only difference is you’ll need to keep track of the parent yourself.
Sure it's a bit messy to swap down a node, but it's not that different from swapping down the value... But if it works it works I guess, lucky your values don't have to be immutable
With only child nodes it's pretty easy to delete the minimum element. If you need to delete an arbitrary node by reference you could search the element and keep a list of ancestors. It's pretty stupid.
I assume you're using a recursive algorythm to search.
Here's how I would do the delete :
Delete method of a node returns a list of it's child nodes (that way you don't lose their reference)
Then you just need to loop over them and add them the same way you would add any other node.
That's a cool idea yeah
The way I ended up doing it is writing a separate method to find the node by its key, so you can just drop into the tree wherever the target node is without coming down from the root. After that I swap the *keys* down towards a leaf. I was trying to move the node itself before but it is much easier to just reassign the keys. This effectively just turns some leaf node into the target node and deletes it without changing the tree structure
You don’t need a parent pointer to remove nodes from a min/max heap. The most simple binary heap is a tree and you descend the tree, thus when you move down to decrease the key (that’s where you’d want to delete a node), you just keep a pointer to the parent.
It's a binary max heap, which means the tree has to be formatted in a specific way and removing stuff from the tree has to maintain that structure. So just connecting the children to the deleted node's parent isn't enough, they also have to get rearranged to maintain the trees structure.
Also the max part means the higher priority node's are closer to the tree's root, and removing is done by bringing the node *away* from the root until it's a leaf and can be removed without affecting any other nodes.
Did the specs say you had to implement it explicitly as a tree structure instead of as an array based heap? In practice, heaps built using an array are more space and time efficient.
Oh gross. I get the complication now. I like your implementation then that you described before in another comment.
So there’s a required amount of allocated memory? Can a node have a null value until it is needed again? I guess it may not matter when you do the node shuffling, just wondering if trying to determine when to do it is worth it vs how fast the operation will realistically run anyway..
Since it’s a binary heap, each node will have at most 2 children, which means you don’t need explicit pointers. If you know the maximum allowed number of children per node beforehand, you can ‘cheat’ by implementing the heap with an array — using indexes as implicit pointers. (Note this technique won’t work for heaps where the number of children is unknown.)
You can set up the array such that for any node at index `i`, its children will be at indices `2*i + 1` and `2*i + 2`. And given any child node at index `j`, its parent will be at `floor((j - 1)/2)`. **(Don’t take my word for it, prove to yourself they will actually work. Draw a picture if you need to.)** As long as you always stick to these rules whenever you read from or write to the heap, your nodes don’t need to have explicit pointers. Check out the [wiki article](https://en.wikipedia.org/wiki/Binary_heap) for details.
ooh yeah we learned about this! seems like a really simple and easy way to go about doing this - probably why they had us make the whole thing out of nodes lol. I probably would have done this if it was an option
they're visualized as binary trees, but really they're just an array. you don't even need pointers to get to a child, just multiply index by 2 and add 1 or 2
When you're later at work somewhere you're supposed to not be the one man team leader doing all the security at Jurassic Park. You need to deal with whatever the team uses, maybe because of library requirements.
It's nice to copy a good algorithm from a book but obviously that's not the given task.
Why are you using a node class for a heap? What?
It's a project at my university. I wouldn't if I didnt have to :(
Which operations does the heap need to be able to do?
Pretty basic stuff, adding, deleting, searching and printing the tree. Delete is screwing me right now but everything else is fine That's actually why I made the meme, having a reference to the nodes parent would make this so much easier
Which is why they won't let you. It allows you to skip some of the logic they want you to learn.
Ok so I figured it out. God I hate it but it works I was trying to rotate the node out of the tree but that was causing a lot of weird problems, so instead I swapped the node's *value* down the tree till it is at a leaf node, and just unlink whatever node the value ends up at from it's parent (which I kept track of every time I descended down the tree). I wrote a separate method to target a node by its value so I don't have to go down from the root when deleting. Because it's a random priority bst the actual node where the value sits doesn't matter, only the value of the node does. Not my best work, but the bit died about four hours ago and it works.
TBH I dont understand any of this shit, but I have been working as a senior for sometime now. I learned it once but havent used it in a while. These things trigger my imposter syndrome
If you asked me to do an infix traversal of a binary tree I'd have to Google the algo. This stuff isn't practical or useful to know but it builds problem solving skills you need later in your career. All that to say, no one remembers all this stuff a year out of college.
Infix isn't complicated once you define the problem. There isn't an algo to remember as long as you know how to traverse trees and what's the order of traversal. Graph coloring, travelling salesman. These should be better googled if you are writing some code for work.
its useful but for very specific tasks that you are kist rarely going to see
Been a senior for a long time now. Never once needed this stuff. You shouldn't feel like an imposter for not knowing something that never comes up in your domain.
These things are only useful if you start implementing your own algorithms from scratch in rendering, compression etc. Nobody does this except as an academic exercise
How boring are the projects you all work on? You never need to push your data structure and algorithm knowledge for anything you do?
What you find boring and what others find boring likely differs. Doing tight algorithm optimization \*can\* be interesting but I usually find it annoying to do in the scheme of the larger problems I'm working with, which are usually in the fullstack range-- I need to create a backend API endpoint, create the right DB queries, and then get it to the frontend, and build good code to render it out. This is all backed by the work I do to make sure the system deploys on its target and is configured correctly. Since I have to do \*\*all\*\* of that, I'm incentivized to find quicker ways of solving a problem rather than having the code itself run more quickly. Most of my stuff is not computationally bound anyway, but latency-bound. Occasionally I do need to optimize an endpoint, but it's rare, and I don't remember the last time I had to actually deal with some complex tree structure in the way described by the OP. Usually a bit of work leveraging hash maps/sets, better specified DB queries and deliberate loop phrasing is enough. Most of the tight algorithm stuff is stable work that's in whatever data structure library I'm working with. No need to learn it-- happy to let someone else handle that so I can ship. I have spent some time learning it anyway just to explore but it still never comes up. If you like doing this kind of work, good for you, please do! We need people doing that and getting senior at it. That kind of drilled down focus is what produces the libraries that people like me use for the problems people like me find interesting. It's a big field out there. :)
I sidestepped all the comp-sci bullshit by doing a physics degree and I'm doing just fine. Not once have I felt the lacked "theory" actually impeded me, but then again I just write webapps rather than anything that cares about efficiency or speed
this comment just validated so much of my own internal psyche thank you.
Welcome to recursive algorithms! A heap is also a fractal. Each node is also a heap, and so you shouldn't need to refer to your parent to figure out the answer to your problem. Each node, each heap, in the heap reports its answer to its parent, and the parent then decides what to do based on the answers it receives. When deleting nodes, you might think "well then I need to rebuild this whole branch." Correct, you do. The easiest way to rebalance is often to just build it again from scratch. So just have a recursive algorithm build a list of all nodes underneath the one you're deleting, build a new heap from those nodes, and tack it onto the existing structure. Is it inefficient? Not really. Rejiggering pointer connections is cheap, and so is the math involved in the comparisons unless you have a complex data type with a difficult value to figure out. At that point, you'd need to perhaps having this comparison value be calculated upon creation of the element rather than at comparison time. It depends on your use-cases.
Addendum: This is true for heaps and other simple data structures. Things like red-black binary search trees do have more optimized algorithms for rebalancing, but you'll learn about those when you get to them. They're not applicable here.
>When deleting nodes, you might think "well then I need to rebuild this whole branch." Correct, you do. The easiest way to rebalance is often to just build it again from scratch. Yup. Had many troubles in Uni trying to program this same project because the rotating and balancing *had* to be done in-place
I wouldn't agree that it's cheap. Lots of small heap allocations have poor cache locality, can make an order of magnitude difference or more easily.
It's good enough for scholastic purposes. If integrating into a standard library, we can fuss about it more.
I mean, it IS the best work, as it's really the only way you can remove a random element from a heap. Moreover, it's exactly the same algo as the one for removing the top element since the subheap is also a heap, the only difference is to restore the link of the subheap's parent. It's easier if you use an array, but the idea is still the same - you sift the element through the heap swapping it with it's bigger priority child until it's gone. The problem is not to remove an element, but to find it, which is not possible to do efficiently unless you use an additional lookup data structure.
Before I was trying to move the entire node, with this I'm only moving the node's values. The tree stricture stays exactly where it is. Makes it so much easier to use that algorithm without managing child positions and rotations and whatnot
I have no idea what you are doing with pointers. A max can be made with an array without any pointers. Only a tiny bit complex but if you already know how to make functions then it's not that complex.
Dude. What you wrote sounds very wrong. A heap is implemented on a variable length array. No rotations are needed, only "bubbling". And certainly no linking / unlinking of nodes. I bet your professors want you to learn to implement a heap the proper way, not the wasteful way. If you need help, hit me up I'm good at this shit.
What’s wrong with storing a reference to the parent and then setting the parent’s next pointer to the current node’s next pointer? If you don’t have a parent pointer the only difference is you’ll need to keep track of the parent yourself.
Sure it's a bit messy to swap down a node, but it's not that different from swapping down the value... But if it works it works I guess, lucky your values don't have to be immutable
I'm trying *so* hard to do that...
U got this!
With only child nodes it's pretty easy to delete the minimum element. If you need to delete an arbitrary node by reference you could search the element and keep a list of ancestors. It's pretty stupid.
If been trying to find a way around that but I think that's the course of action here. *Shudders*
I assume you're using a recursive algorythm to search. Here's how I would do the delete : Delete method of a node returns a list of it's child nodes (that way you don't lose their reference) Then you just need to loop over them and add them the same way you would add any other node.
That's a cool idea yeah The way I ended up doing it is writing a separate method to find the node by its key, so you can just drop into the tree wherever the target node is without coming down from the root. After that I swap the *keys* down towards a leaf. I was trying to move the node itself before but it is much easier to just reassign the keys. This effectively just turns some leaf node into the target node and deletes it without changing the tree structure
You don’t need a parent pointer to remove nodes from a min/max heap. The most simple binary heap is a tree and you descend the tree, thus when you move down to decrease the key (that’s where you’d want to delete a node), you just keep a pointer to the parent.
Does deleting a node not just mean finding said node’s root and stem and connecting those then unallocating the memory?
It's a binary max heap, which means the tree has to be formatted in a specific way and removing stuff from the tree has to maintain that structure. So just connecting the children to the deleted node's parent isn't enough, they also have to get rearranged to maintain the trees structure. Also the max part means the higher priority node's are closer to the tree's root, and removing is done by bringing the node *away* from the root until it's a leaf and can be removed without affecting any other nodes.
Did the specs say you had to implement it explicitly as a tree structure instead of as an array based heap? In practice, heaps built using an array are more space and time efficient.
Yeah they specified nodes
Oh gross. I get the complication now. I like your implementation then that you described before in another comment. So there’s a required amount of allocated memory? Can a node have a null value until it is needed again? I guess it may not matter when you do the node shuffling, just wondering if trying to determine when to do it is worth it vs how fast the operation will realistically run anyway..
Since it’s a binary heap, each node will have at most 2 children, which means you don’t need explicit pointers. If you know the maximum allowed number of children per node beforehand, you can ‘cheat’ by implementing the heap with an array — using indexes as implicit pointers. (Note this technique won’t work for heaps where the number of children is unknown.) You can set up the array such that for any node at index `i`, its children will be at indices `2*i + 1` and `2*i + 2`. And given any child node at index `j`, its parent will be at `floor((j - 1)/2)`. **(Don’t take my word for it, prove to yourself they will actually work. Draw a picture if you need to.)** As long as you always stick to these rules whenever you read from or write to the heap, your nodes don’t need to have explicit pointers. Check out the [wiki article](https://en.wikipedia.org/wiki/Binary_heap) for details.
ooh yeah we learned about this! seems like a really simple and easy way to go about doing this - probably why they had us make the whole thing out of nodes lol. I probably would have done this if it was an option
Watch professor Sedgwick algorithms course on coursera. It is free and I haven't seen a better explanation.
aren't heaps just binary trees? why do you need a parent pointer? left & right pointers should be enough
they're visualized as binary trees, but really they're just an array. you don't even need pointers to get to a child, just multiply index by 2 and add 1 or 2
For anyone scrolling. This is correct, and it works because a heap is a "complete binary tree." I had to scroll pretty far to find this...
Use an array?
I wish
It’s obligatory to use nodes?
Yeah it is, this is for a university course so they have weird specifications sometimes
Use an array of Node objects?
Oh my god I could have done that...
It's not a pointer. It's a memory arena handle 😎
Well then. An array of nodes
That sucks, hope you finish soon
When you're later at work somewhere you're supposed to not be the one man team leader doing all the security at Jurassic Park. You need to deal with whatever the team uses, maybe because of library requirements. It's nice to copy a good algorithm from a book but obviously that's not the given task.
If you add a parent pointer you are no longer using a tree but a graph
Trees and linked lists are specialized graphs
Of course, but you know what I'm talking about, don't be that guy
Sure I do
Least asocial c# dev
Do discussions about the nature of data structures come up often socially for you? They don't for me
Sure, now go on with your life cuz
yeah but they meant you're using a graph that is not a tree
Yes
This sub really is first year undergrad.
Recursion is your friend here.
My man. Learn recursion and read up the theory on heaps. No need for a parent pointer!
I guess you have to traverse to the leaf and record the references to the nodes you hit on insert. remove shouldn't be too different though. gl
Just make terminal nodes point back to the root node as a "child," and traverse it cyclically, EZ
Mind if I ask what uni you in?
Make a different node inplementation
Array bro