Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- private void adjustHeap(int index)//This is a MinHeap (higher value = lower position in tree)
- {
- //Percolates down if one child is larger
- int leftChildPos = (2*index) + 1;
- int rightChildPos = (2*index) + 2;
- T current = _items.getElementAt(index);
- T leftChild = _items.getElementAt(2);
- T rightChild = _items.getElementAt(rightChildPos);
- if(leftChildPos >= _items._number_of_items)//You are a leaf
- {
- //No child exists, do nothing
- }
- else if(rightChildPos >= _items._number_of_items)//Does right child NOT exist
- {
- //Left child exists
- if(current.compareTo(leftChild) > 0)
- {
- _items.setElementAt(current, leftChildPos);
- _items.setElementAt(leftChild, index);
- index = leftChildPos;
- adjustHeap(index);
- }
- }
- else//Compare to left since right doesn't exist
- {
- //Left child exists and right
- if(current.compareTo(leftChild) > 0)
- {
- if(leftChild.compareTo(rightChild) < 0)//leftChild < rightChild
- {
- _items.setElementAt(current, leftChildPos);
- _items.setElementAt(leftChild, index);
- index = leftChildPos;
- adjustHeap(index);
- }
- else if(current.compareTo(rightChild) > 0)//If rightChild < leftChild
- {
- //Swap and call itself
- _items.setElementAt(current, rightChildPos);
- _items.setElementAt(rightChild, index);
- index = rightChildPos;
- adjustHeap(index);
- }
- }
- else if(current.compareTo(rightChild) > 0)
- {
- //Swap and call itself
- _items.setElementAt(current, rightChildPos);
- _items.setElementAt(rightChild, index);
- index = rightChildPos;
- adjustHeap(index);
- }
- }
- }
- @Override
- public T getElementAt(int index) {
- // TODO Auto-generated method stub
- if (index < 0 || index >= _number_of_items)
- {
- throw new IndexOutOfBoundsException();
- }
- return _items[index];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement