使用最小堆对单词进行排序

Question

我正在学习使用堆，作为练习，我正在尝试使用堆 class 我创建的用于排序单词的程序。我已经从文件中读入单词并成功将它们添加到堆中。我在弄清楚如何打印出排序的单词列表时遇到了一些麻烦。根据我对最小堆工作原理的理解，如果我从 min/root 节点中删除它们，它们将始终按排序顺序删除。到目前为止，我已经尝试做一个简单的 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();
}

这是我堆中的删除函数Class

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

Answer 1

我猜想 remove() 将堆大小减少 1。因此，对于循环的每次迭代，您将 i 增加 1，并将堆大小减少 1。我会更改为堆大小 >0.

时运行的 while 循环

使用最小堆对单词进行排序

Using a Min-Heap to Sort Words

java

sorting

heap

min-heap