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

: 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
:


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.

thanks, using Integer is a good idea.

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.

: thanks, using Integer is a good idea.
:
: 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.

this case is actually easy and I already did it in recursion (in case I extract the max)

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.

: this case is actually easy and I already did it in recursion (in case I extract the max)
:
: 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.

thanks, just what I wanted to hear.

I actually do want to do a binary heap not a tree, so i\ll just remove that chosen item removale method and than i'm done I gues..

thanks!

: thanks, just what I wanted to hear.
:
: I actually do want to do a binary heap not a tree, so i\ll 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.

ok, but I do want to do a heap, nothing else. :)

thank you