堆书盒包装

Question

我正在尝试编写一个程序，该程序按顺序读取书籍，将它们存储在堆中，并实现贪婪算法，根据重量将书籍有效地装入盒子中；

我在正确实现堆时遇到问题。

我用来添加到堆的方法称为 addLastChild()。它应该找到堆中的下一个位置并插入新书并根据其重量进行重组。

这是添加代码：

public void addLastChild(Book newBook)
{
    Book[] pathList = new Book[30];
    int tracker = 0;

    int cnt = BookCnt+1;
    String path = "";
    while(cnt >= 1) 
    {
        path = (cnt %2) + path;
        cnt = cnt / 2;
    }

    Book c = root;

    if(root!=null)
    {
        pathList[tracker]=root;
        tracker++;
    }

    for(int i = 1; i < path.length()-1; i++){
        if(path.charAt(i)== '0') {

            c = c.left;
            pathList[tracker]=c;
            tracker++;
        } else {

            c = c.right;
            pathList[tracker]=c;
            tracker++;
        }
    }
    if(path.length() == 1)
    {
        root = newBook;
    } 
    else if(path.charAt(path.length()-1)== '0') {
        c.left = newBook;
        pathList[tracker]=c.left;
        tracker++;

    } 
    else
    {
        c.right = newBook;
        pathList[tracker]=c.right;
        tracker++;
    }
    BookCnt++;

    boolean doTrickle = false;
    if(tracker>=2)
    {
        doTrickle = true;
    }

    while(doTrickle == true)
    {
        Book temp = new Book(pathList[tracker-2].refNumber, pathList[tracker-2].weight, pathList[tracker-2].title, null,null);
        //int refNumber, int weight, String title, Book left, Book right
        print(root,"    ");

        if(pathList[tracker-1].weight > pathList[tracker-2].weight)
        {

            pathList[tracker-2].refNumber=pathList[tracker-1].refNumber;

            pathList[tracker-2].title=pathList[tracker-1].title;
            pathList[tracker-2].weight=pathList[tracker-1].weight;

            if(pathList[tracker-2].left == pathList[tracker-1])
            {
                pathList[tracker-2].left = temp;
            }
            if(pathList[tracker-2].right == pathList[tracker-1])
            {
                pathList[tracker-2].right = temp;
            }

            tracker--;

            System.out.println("we trickled");
            print(root,"    ");
        }
        else
        {
            doTrickle =false;
        }
    }

}

我用来从堆中删除的两个方法是removeLastChild()和remove()，removeLastChild()方法返回堆中的最后一本书，remove()应该返回带有最大权重并用最后一本书替换根，然后相应地重组堆。

这是给我带来麻烦的删除代码：

Book removeLastChild() {
    int cnt = BookCnt;
    String path = "";
    while(cnt >= 1) 
    {
        path = (cnt %2) + path;
        cnt = cnt / 2;
    }

    Book returnBook = null;
    Book c = root;
    for(int i = 1; i < path.length()-1; i++){
        if(path.charAt(i)== '0') {
            c = c.left;
        } else {
            c = c.right;
        }
    }
    if(path.length() == 1)
    {
        returnBook = root;
        root = null;
    } 
    else if(path.charAt(path.length()-1)== '0') {
        returnBook = c.left;
        c.left = null;
    } 
    else
    {
        returnBook = c.right;
        c.right = null;
    }
    BookCnt--;
    return returnBook;
}

Book remove()
{

    Book largest =root; 
    root = removeLastChild();

    if(largest.left!= null)
    {
        root.left = largest.left;
    }
    if(largest.right!= null)
    {
        root.right = largest.right;
    }



    Book cur = root;

    if(root!= null)
    {
        while(cur.left !=null && cur.right!= null)
        {
            if(cur.weight<cur.left.weight || cur.weight<cur.right.weight)
            {
                Book temp = new Book(cur.refNumber, cur.weight, cur.title, null, null);
                //int refNumber, int weight, String title, Book left, Book right

                if(cur.left.weight>cur.right.weight)
                {
                        cur.refNumber = cur.left.refNumber;

                    cur.title = cur.left.title;
                    cur.weight = cur.left.weight;


                    cur.left.refNumber = temp.refNumber;
                    cur.left.weight = temp.weight;
                    cur.left.title = temp.title;
                    cur = cur.left;

                }
                else
                {

                    cur.refNumber = cur.right.refNumber;

                    cur.title = cur.right.title;
                    cur.weight = cur.right.weight;

                    cur.right.refNumber = temp.refNumber;
                    cur.right.weight = temp.weight;
                    cur.right.title = temp.title;
                    cur = cur.right;

                }

            }
            else
            {
                return largest;
            }
        }
    }
    return largest;

}

感谢您的帮助！

我很乐意澄清任何我没有表达清楚的事情。

Answer 1

如果我建议您的堆实现的替代方案，并考虑到背包问题的贪婪算法的目标，为什么不简单地使用 PriorityQueue？

来自文档：“基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序进行排序，或者通过在队列构造时提供的比较器进行排序（...）”

如果您的书籍类实现了像这样的类似界面（示例中的书非常简化）：

    class Book implements Comparable<Book>{
        public String title;
        public int weight;

        public Book(int weight, String title) {
            this.weight = weight;
            this.title = title;
        }

        @Override
        public int compareTo(Book anotherBook) {
            return weight - anotherBook.weight;
        }
    }

书籍的自然排序应该从重量最小的书到重量最大的书。

在优先级队列中使用 Book 类：

    public static void main(String[] args) {
        Book book1 = new Book(10,"a");
        Book book2 = new Book(11,"b");
        Book book3 = new Book(20,"c");
        Book book4 = new Book(20,"d");
        Book book5 = new Book(11,"e");

        PriorityQueue<Book> bookQueue = new PriorityQueue<Book>();
        bookQueue.add(book1);
        bookQueue.add(book2);
        bookQueue.add(book3);
        bookQueue.add(book4);
        bookQueue.add(book5);

        while(!bookQueue.isEmpty()){
            Book book = bookQueue.poll();
            System.out.println(book.title + " - " + book.weight);
        }
    }

您应该能够按照需要将书籍放入盒子中的方式迭代书籍。