最大堆插入无法正常工作

Question

我正在尝试在 java 中实现一个堆。我正在测试插入。当我在 Heaper class 的插入方法中插入元素并打印出树时，我收到的输出是

[1]

[1, 16]

[16, 1, 1, 16, 4]

[16, 4, 1, 1, 16, 1, 4, 23]

关于为什么会发生这种情况有什么想法吗？谢谢！

主要方法

public class HeapTester {


public static void main(String[] args) {
   Heaper heap = new Heaper();
   heap.insert(1);
   heap.insert(16);
   heap.insert(4);
   heap.insert(23);


}}

堆Class

    package heaptester;

    import java.util.ArrayList;


    public class Heaper {
     private ArrayList<Integer> tree;



    /**

    * Constructs an empty heap

    */

public Heaper()

{

tree=new ArrayList<Integer>();

}

public boolean isEmpty()

{

if (tree.size() == 0)

{

return true;

}

return false;



}



public void insert(Integer obj)

{

if (isEmpty())

{

tree.add(obj);
System.out.println(tree);

}

else

{



int place = tree.size()-1;

int parent = (place -1)/2;



while(parent >= 0 && (tree.get(place) > tree.get(parent)))

{

swap(tree, place, parent);

place=parent;

parent = (place -1)/2;

}
tree.add(obj);
System.out.println(tree);

}

}

public Integer remove()

{

Integer root = tree.get(0);

tree.set(0 , tree.get(tree.size()-1));
System.out.println(tree);
reheapify(0);
System.out.println(tree);
return root;

}

public Integer peek()

{

return tree.get(0);

}

public int size()

{

return tree.size();

}

/**

* Swaps a parent and child elements of this heap at the specified indices

* @param place an index of the child element on this heap

* @param parent an index of the parent element on this heap

*/

private void swap(ArrayList<Integer> tree, int place, int parent)

{

Integer temp=tree.get(place);

tree.add(place, tree.get(parent));

tree.add(parent, temp);


}

/**

* Rebuilds the heap to ensure that the heap property of the tree is preserved.

* @param root the root index of the subtree to be rebuilt

*/

private void reheapify(int root)

{

if (!isLeaf(root))

{

if ( (tree.get(root) < tree.get(leftChild(root))) || (tree.get(root) < tree.get(rightChild(root))))

{

if (tree.get(leftChild(root)) > tree.get(rightChild(root)))

{

swap(tree,root, leftChild(root));

reheapify(leftChild(root));

}else

{

swap(tree,root, rightChild(root));

reheapify(rightChild(root));

}

}

}

}

private int leftChild(int pos)

{

return (2 * pos);

}

private int rightChild(int pos)

{

return (2 * pos) + 1;

}

private boolean isLeaf(int pos)

{

if (pos >= (size() / 2) && pos <= size())

{

return true;

}

return false;

}

}

Answer 1

在您的插入方法中，您应该在获取树的大小之前将 obj 值添加到树中。

public void insert(Integer obj)

{

 //...
else
{
    tree.add(obj)
    int place = tree.size()-1;
    int parent = (place -1)/2;

    while(parent >= 0 && (tree.get(place) > tree.get(parent)))
    {
        swap(tree, place, parent);
        place=parent;
        parent = (place -1)/2;
    }
    System.out.println(tree);

}

最大堆插入无法正常工作

Max Heap Insertion Not Working Properly

java

heap

insert

arraylist