0

我正在学习使用堆，作为练习，我正在尝试使用我创建的堆类来编写一个程序来对单词进行排序。我已从文件中读取单词并将它们成功添加到堆中。我在弄清楚如何打印出单词的排序列表时遇到了一些麻烦。根据我对最小堆如何工作的理解，如果我从最小/根节点中删除，它们将始终按排序顺序删除。到目前为止，我已经尝试过做一个简单的 for 循环，但是只有一半的堆被删除了。

我的主要尝试

public static void main(String[] args) {
    Heap heap = new Heap();
    heap = read( heap ); 

    for( int i = 0; i < heap.getSize(); i++){
        heap.removeMin();
    }
    heap.printHeap();
}

这是我的堆类中的删除函数

public Node removeMin(){
    Node min = heap.get(0);
    int index = heap.size() - 1;
    Node last = heap.remove(index);
    if( index > 0 ){
        heap.set( 0, last );
        Node root = heap.get(0);
        int end = heap.size() - 1;
        index  = 0;
        boolean done = false;
        while(!done){
            if(getLCLoc(index) <= end ){
                //left exists
                Node child = getNodeAt( getLCLoc(index) );
                int childLoc = getLCLoc(index);
                if( getRCLoc(index) <= end ){
                    //right exists
                    if( getNodeAt( getRCLoc(index) ).getData().compareToIgnoreCase( child.getData() ) < 0 ){
                        child = getNodeAt( getRCLoc(index) );
                        childLoc = getRCLoc(index);
                    }
                }
                if(child.getData().compareToIgnoreCase( root.getData() ) < 0 ){
                    heap.set( index, child );
                    index = childLoc;
                }else{
                    done = true;
                }
            }else{
                //no children
                done = true;
            }
        }
        heap.set( index, root );
    }
    return min;
}
4

1 回答 1

1

我猜想这会将remove()堆大小减小 1。因此，对于循环的每次迭代，您将递增i1 并将堆大小递减 1。我将更改为在 heapsize > 0 时运行的 while 循环。

于 2015-05-06T00:44:52.727 回答