A problem with a heap

Comments

• Vilanye

  March 2005

  : 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.
  
• ronenm

  March 2005

  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.
  
• Vilanye

  March 2005

  : 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.
  
• ronenm

  March 2005

  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.
  
• Vilanye

  March 2005

  : 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.
  
  
• ronenm

  March 2005

  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!
  
• Vilanye

  March 2005

  : 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.
  
• ronenm

  March 2005

  ok, but I do want to do a heap, nothing else.
  
  thank you