Упаковка книжной коробки кучи

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

}

2 метода, которые я использую для удаления из кучи, - это 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 ?

Из документации: «Неограниченная приоритетная очередь на основе кучи приоритетов. Элементы приоритетной очереди упорядочены в соответствии с их естественным порядком или компаратором, предоставленным во время построения очереди (...)»

Если ваша книгаКласс реализует интерфейс Comparable следующим образом (книга в примере очень упрощена):

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

Вы должны иметь возможность перебирать книги так, как вам нужно поместить их в свои ящики.