Java: Recursive reheapUp (bubbleUp) method for Heap data structure

Question

I've been trying to write a recursive method that reshapes a heap data structure when an element is enqueued, but I cannot get it to work correctly.

I was able to get a perfectly working recursive reheapDown method, so I have no idea why this one won't work. Here is the class I've been working on, which includes the iterative version of reheapUp which I'm using as a template for designing the recursive version:

public class Heap<T extends Comparable<T>> implements PriQueueInterface<T>
{
  private ArrayList<T> elements;  // priority queue elements
  private int lastIndex;          // index of last element in priority queue
  private int maxIndex;           // index of last position in ArrayList

  public Heap(int maxSize)
  {
    elements = new ArrayList<T>(maxSize);
    lastIndex = -1;
    maxIndex = maxSize - 1;
  }

  public boolean isEmpty()
  // Returns true if this priority queue is empty; otherwise, returns false.
  {
    return (lastIndex == -1);
  }

  public boolean isFull()
  // Returns true if this priority queue is full; otherwise, returns false.
  {
    return (lastIndex == maxIndex);
  }

  private void reheapUp(T element)
  // Current lastIndex position is empty.
  // Inserts element into the tree and ensures shape and order properties.
  {
    int hole = lastIndex;
    while ((hole > 0)    // hole is not root and element > hole's parent
           &&                                               
      (element.compareTo(elements.get((hole - 1) / 2)) > 0)) 
      {
      // move hole's parent down and then move hole up
      elements.set(hole,elements.get((hole - 1) / 2)); 
      hole = (hole - 1) / 2;                                
    }
    elements.set(hole, element);  // place element into final hole
  }

  private void recReheapUp(T element)
  {
    int hole = lastIndex;

    //hole is not root and element > hole's parent
    if (hole > 0)
    {
      if (element.compareTo(elements.get((hole - 1) / 2)) > 0)
      {
        elements.set(hole,elements.get((hole - 1) / 2));
        hole = (hole - 1) / 2;
      }
    }

    //base condition
    if (hole == 0 && element.compareTo(elements.get((hole - 1) / 2)) <= 0))
    {
      elements.set(hole, element);  // place element into final hole
      return;
    }

    recReheapUp(element);
  }

  public void enqueue(T element) throws PriQOverflowException
  // Throws PriQOverflowException if this priority queue is full;
  // otherwise, adds element to this priority queue.
  {
    if (lastIndex == maxIndex)
      throw new PriQOverflowException("Priority queue is full");
    else
    {
      lastIndex++;
      elements.add(lastIndex,element);
      recReheapUp(element);
    }
  }

The reheapUp() and recReheapUp() methods are called whenever an item is enqueued into the heap. I've reworked the recReheapUp() method so many times it's not even worth posting all the changes I've attempted.

I will say that I think the issue lies in my base case, although there may be logical flaws in the general case as well.

I keep getting stack overflow errors no matter what I do, which tells me the recursive method isn't terminating properly. I just recently switched to nested if statements for my recursive method, but I'm not sure if that helped or hurt my cause.

Answer 1

Looks like you're getting stuck in unbounded recursive calls not because there's anything wrong with your base case (although I'm not sure I understand what the inner comparison is for), but because you're effectively calling Heapify on the same element. Your recursive algorithm should know the index of the current element that may need to sift. Something like this:

private void insert(ArrayList<T> heap, T element) {
  head.add(element);
  heapify(heap, heap.size() - 1);
}

private void heapify(ArrayList<T> heap, int location) {
  int parent = (location - 1) / 2; // -1 for zero-indexed language
  // same-element comparison is OK. This will always happen at the root.
  if (heap.get(parent).compareTo(heap.get(location)) > 0) {
    swap(heap, location, parent);
    heapify(heap, parent);
  }
}

private void swap(ArrayList<T> heap, int a, int b) {
  T temp = heap.get(a);
  heap.set(a, heap.get(b));
  heap.set(b, temp);
}

CLRS has a really excellent discussion on Heaps on pages 151-159.