Advertisement
Guest User

recursiveBubbleDown

a guest
Mar 28th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.84 KB | None | 0 0
  1. private void adjustHeap(int index)//This is a MinHeap (higher value = lower position in tree)
  2. {
  3. //Percolates down if one child is larger
  4. int leftChildPos = (2*index) + 1;
  5. int rightChildPos = (2*index) + 2;
  6. T current = _items.getElementAt(index);
  7. T leftChild = _items.getElementAt(2);
  8. T rightChild = _items.getElementAt(rightChildPos);
  9.  
  10. if(leftChildPos >= _items._number_of_items)//You are a leaf
  11. {
  12. //No child exists, do nothing
  13. }
  14. else if(rightChildPos >= _items._number_of_items)//Does right child NOT exist
  15. {
  16. //Left child exists
  17. if(current.compareTo(leftChild) > 0)
  18. {
  19. _items.setElementAt(current, leftChildPos);
  20. _items.setElementAt(leftChild, index);
  21. index = leftChildPos;
  22. adjustHeap(index);
  23. }
  24. }
  25. else//Compare to left since right doesn't exist
  26. {
  27. //Left child exists and right
  28. if(current.compareTo(leftChild) > 0)
  29. {
  30. if(leftChild.compareTo(rightChild) < 0)//leftChild < rightChild
  31. {
  32. _items.setElementAt(current, leftChildPos);
  33. _items.setElementAt(leftChild, index);
  34. index = leftChildPos;
  35. adjustHeap(index);
  36. }
  37. else if(current.compareTo(rightChild) > 0)//If rightChild < leftChild
  38. {
  39. //Swap and call itself
  40. _items.setElementAt(current, rightChildPos);
  41. _items.setElementAt(rightChild, index);
  42. index = rightChildPos;
  43. adjustHeap(index);
  44. }
  45. }
  46. else if(current.compareTo(rightChild) > 0)
  47. {
  48. //Swap and call itself
  49. _items.setElementAt(current, rightChildPos);
  50. _items.setElementAt(rightChild, index);
  51. index = rightChildPos;
  52. adjustHeap(index);
  53. }
  54. }
  55. }
  56.  
  57. @Override
  58. public T getElementAt(int index) {
  59. // TODO Auto-generated method stub
  60. if (index < 0 || index >= _number_of_items)
  61. {
  62. throw new IndexOutOfBoundsException();
  63. }
  64.  
  65. return _items[index];
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement