Java: Heap数据结构的递归reheapUp(bubbleUp)方法

Question

我一直在尝试编写一种递归方法，在元素入队时重塑堆数据结构，但我无法使其正常工作。

我能够得到一个完美工作的递归 reheapDown 方法，所以我不知道为什么这个方法不起作用。这是我一直在研究的 class，其中包括我用作设计递归版本模板的 reheapUp 的迭代版本：

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);
    }
  }

每当将项目排入堆时，将调用 reheapUp() 和 recReheapUp() 方法。我已经多次修改 recReheapUp() 方法，甚至不值得发布我尝试过的所有更改。

我会说我认为问题出在我的基本情况下，尽管一般情况下也可能存在逻辑缺陷。

无论我做什么，我总是收到堆栈溢出错误，这告诉我递归方法没有正确终止。我最近刚刚为我的递归方法切换到嵌套的 if 语句，但我不确定这是否有助于或伤害我的事业。

Answer 1

看起来你陷入无限递归调用并不是因为你的基本情况有什么问题（尽管我不确定我是否理解内部比较的目的），而是因为你有效地调用了 Heapify在同一个元素上。您的递归算法应该知道可能需要筛选的当前元素的索引。像这样：

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 在第 151-159 页对堆进行了非常精彩的讨论。

Java: Heap数据结构的递归reheapUp(bubbleUp)方法

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

java

heap

recursion