I'm trying to create an integer array that represents a heap.
I am almost finished, but still have two little problems.
when I remove an item, I set the heap to replace the removed item with the last item of the array and then call a method to re-organize the heap.
problem is that I can't seem to do it well, so any tips are welcome.
second problem is that since it is an integer array I had to make up a rule that if the number 0 occupies a spot in the heap, it means there is nothing there, but I want to be able to add the number 0 to the heap, so how can I fix that?
thanks
Comments
:
: I am almost finished, but still have two little problems.
:
: when I remove an item, I set the heap to replace the removed item with the last item of the array and then call a method to re-organize the heap.
:
: problem is that I can't seem to do it well, so any tips are welcome.
:
: second problem is that since it is an integer array I had to make up a rule that if the number 0 occupies a spot in the heap, it means there is nothing there, but I want to be able to add the number 0 to the heap, so how can I fix that?
:
: thanks
:
You can't use 0 for both, so you could disallow negative integers and use -1 as you did for 0, or you could use the Integer class, and use null to mean nothing is there.
still I do not know how to be able to arrange the heap again once an item has been removed from it.
Already solved arrangement of the heap in case I add an item though.
:
: still I do not know how to be able to arrange the heap again once an item has been removed from it.
:
: Already solved arrangement of the heap in case I add an item though.
:
Even though the heap is in an array, it helps to think of it as a binary tree.
This is going from memory but I think it is right.
To delete, you can only remove the root, which is the highest or lowest value depending on whether it is a min or maxheap. Swap the root with the last value, set it to null, decrement the size of the heap. Then reset it to a valid heap. Recursion is definately your friend when doing this. The value that is now the root is at index 0, so check it against indices 1 & 2, if either value is higher(or lower if a minheap) swap them, if you do a swap check the 2 leaves under it. And so on. If you swap the root with index 2, then the next values you check are indices 5 & 6. Draw a binary tree and it is easier to visualize.
Hope this is helpful.
What I want is to allow someone to choose any item on the heap array and remove it just by giving the item.
so if the item you want to remove is 5 and assuming it is in the heap somewhere, the item will be removed and the last item in the array will be put in its place.
in this case, I do not know where exactly the item I want to sort is located so I cannot deal with it with the same recursion, since I'm not necessarely starting from the root.
:
: What I want is to allow someone to choose any item on the heap array and remove it just by giving the item.
:
: so if the item you want to remove is 5 and assuming it is in the heap somewhere, the item will be removed and the last item in the array will be put in its place.
:
: in this case, I do not know where exactly the item I want to sort is located so I cannot deal with it with the same recursion, since I'm not necessarely starting from the root.
:
Technically speaking, what you want to do is an array based implemention of a binary tree, not a heap.
You can still recursively search for the item and you want to start at the root regardless. Just like in a binary tree, you start at the root, it will be similar to your insert, after you have inserted the new item at the end of the array.
I actually do want to do a binary heap not a tree, so ill just remove that chosen item removale method and than i'm done I gues..
thanks!
:
: I actually do want to do a binary heap not a tree, so ill just remove that chosen item removale method and than i'm done I gues..
:
: thanks!
:
What I meant was that what you are describing is not a heap but an array based implemention of a binary tree. A heap is sort of like a modified stack. In a heap, you can only remove the first item, but unlike a stack, the remaining data will get shifted around after a removal.
What you are doing is fine, but it isn't a heap.
Your welcome, I hope I helpful.
thank you