Java Arraylist 堆实现

Question

我正在尝试为基于数组列表的堆实现实现一个 insert() 方法，但是每当我测试插入多个整数的方法时，其中至少有一个大于 ~4，程序需要永远运行。例如，在 main 函数中一起声明 heap.insert(1) 和 heap.insert(8) 将永远占用运行。这是我的堆 class:

import java.util.*;


public class Heap<E extends Comparable<E>> implements HeapAPI<E>
{
    /**
     * A complete tree stored in an array list representing this
     * binary heap
     */
    private ArrayList<E> tree;

    /**
     * Constructs an empty heap
     */
    public Heap()
    {
        tree = new ArrayList<E>();
    }

    public boolean isEmpty()
    {
       return tree.isEmpty();
    }

    public void insert(E obj)
    {
        tree.add(tree.size(), obj);
        siftUp(tree.size() - 1);
    }

    /**
     * siftUp from position k. The key or node value at position
     * may be greater that that of its parent at k/2.
     * @param k position in the heap arraylist
     */
    private void siftUp(int k)
    {
        E v = tree.get(k);
        while (v.compareTo(tree.get(k / 2)) == 1)
        {
            tree.add(k, tree.get(k / 2));
            k = k / 2;
        }
        tree.add(k, v);
    }

    public int size()
    {
       return tree.size();
    }
}

这是我的教授给我们的伪代码，我从以下方面对 insert() 和 siftUp() 方法进行了建模：

该程序适用于小整数，例如，如果我连续多次键入 heap.insert(1)，但如果我将其中一个数字更改为更大的数字，则永远不会完成运行ning整数。没有错误被抛出，因为当我尝试运行程序时它没有完成执行。我不确定发生了什么。感谢任何帮助。

Answer 1

让我们暂时浏览一下您的代码：

public void insert(E obj)
{
    tree.add(tree.size(), obj);
    siftUp(tree.size() - 1);
}

private void siftUp(int k)
{
    E v = tree.get(k);
    while (v.compareTo(tree.get(k / 2)) == 1)
    {
        tree.add(k, tree.get(k / 2));
        k = k / 2;
    }
    tree.add(k, v);
}

现在，您执行 tree.insert(1)，一切正常。接下来你调用 tree.insert(0)。让我们看看会发生什么。

tree.add(tree.size(), obj) 添加 0 作为数组列表中的下一项。所以你现在有一个包含 [1, 0]
代码调用siftUp(1)
在siftUp中，第一行从数组列表中获取元素1。此时，v = 1
在 while 语句中，代码将值 1 与 tree[k/2] 处的值进行比较。由于 k == 1，您正在检查根节点（即 tree[0]），我们知道它等于 1.
因为新值小于其 parent，您将 parent 值复制到新项目的位置。此时，您的数组列表包含 [1, 1].
您将索引 k 除以 2，得到 0。
现在您回到了 while 状态。 k 等于 0 而 tree[k] 处的值为 1，这意味着它仍然大于 v.
您现在处于无限循环中，不断将索引 0 处的值与您的临时值进行比较。

问题是你的循环没有明确的结束条件。

解决问题的一种方法是如果k == 0.

结束循环

private void siftUp(int k)
{
    E v = tree.get(k);
    while (k > 0 && v.compareTo(tree.get(k / 2)) == 1)
    {
        tree.add(k, tree.get(k / 2));
        k = k / 2;
    }
    tree.add(k, v);
}

下一个麻烦是您对 parent 节点的计算不正确。如果堆的根节点在索引0处，那么对于索引ix处的节点，它的左child在(ix*2)+1，右child在(ix*2)+2。节点的 parent 位于 (ix-1)/2.

考虑具有三个节点的堆：

        0
      1   2

此处的节点编号与数组索引相同

如果根在索引0，那么左节点在(2 * 0) + 1。右节点在(2 * 0) + 2。1的parent是( 1-1)/2。而 2 的 parent 是 (2-1)/2。在您的代码中，您 parent 的计算结果是 k/2，这将为上面堆中标记为 2 的节点给出不正确的值 1。

Java Arraylist 堆实现

Java Arraylist Heap Implementation

java

algorithm

heap

arraylist

data-structures