A problem with a heap

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'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 ill 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 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.
  • ok, but I do want to do a heap, nothing else. :)

    thank you
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories