Восстановить состояние кучи во всей куче

Я пытаюсь ответить на следующий вопрос программирования:

В программе heap.java метод insert() вставляет новый узел в кучу и обеспечивает сохранение состояния кучи. Напишите метод toss(), который помещает новый узел в массив кучи, не пытаясь поддерживать состояние кучи. (Возможно, каждый новый элемент можно просто поместить в конец массива.) Затем напишите метод restoreHeap(), который восстанавливает состояние кучи по всей куче. Использование toss(), за которым следует один restoreHeap(), более эффективно, чем многократное использование insert(), когда за один раз необходимо вставить большой объем данных. См. описание пирамидальной сортировки для подсказок. Чтобы проверить свою программу, вставьте несколько элементов, добавьте еще несколько, а затем восстановите кучу.

Я написал код для функции toss, которая успешно вставляет узел в конец и не изменяет состояние кучи. У меня проблемы с функцией restoreHeap, и я не могу понять это. Я включил две функции ниже.

Полный код heap.java находится здесь (включая toss() и restoreHeap() )

toss() — я взял за основу функцию вставки

public boolean toss(int key)
{
    if(currentSize==maxSize)
        return false;
    Node newNode = new Node(key);
    heapArray[currentSize] = newNode;
    currentSize++;
    return true;
}  // end toss()

restoreHeap() — Я основывал это на функцииrickleUp и получаю StackOverflowError.

public void restoreHeap(int index)
{
    int parent = (index-1) / 2;
    Node bottom = heapArray[index];

    while( index > 0 &&
            heapArray[parent].getKey() < bottom.getKey() )
    {
        heapArray[index] = heapArray[parent];  // move it down
        index = parent;
        parent = (parent-1) / 2;
    }  // end while
    heapArray[index] = bottom;
    while(index != 0)
    {
        restoreHeap(parent++);
    }

}  // end restoreHeap()

Есть идеи? Помощь приветствуется.


java heap heapsort
person Rishad Bharucha    schedule 29.03.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я попробую. Вот способ сделать то, что вы просили, с некоторыми пояснениями.

Поскольку вы знаете, что половина всех узлов в куче являются листами, а лист сам по себе является допустимой кучей, вам нужно только просмотреть другую половину узлов, чтобы убедиться, что они также являются допустимыми. Если мы делаем это снизу вверх, мы можем поддерживать правильную структуру кучи «внизу», когда мы поднимаемся по куче. Это легко сделать с помощью цикла for:

 public void rebuildHeap()
 {
    int half = heapArray.length / 2;
    for(int i = half; i >= 0; i--)
        restoreHeap(i);
 }

Как тогда реализован restoreHeap? Предполагается, что узел index проверяется на соответствие его дочерним элементам, чтобы узнать, нужно ли переместить узел. Поскольку мы убедились, что деревья ниже узла index являются кучами, нам нужно только переместить узел index в правильное положение. Следовательно, мы перемещаем его вниз по дереву.

Сначала нам нужно найти детей. Поскольку каждая строка из трех содержит в два раза больше узлов, чем предыдущая строка, дочерние элементы могут быть расположены следующим образом:

private void restoreHeap(int index)
{
    int leftChild = (index * 2) + 1;  //+1 because arrays start at 0
    int rightChild = leftChild +1;
    ...

Теперь вам просто нужно сравнить значение детей со значением index узлов. Если дочерний элемент имеет большее значение, вам необходимо поменять местами узел index с дочерним узлом. Если оба дочерних элемента имеют большее значение, вам необходимо поменять местами дочерний элемент с наибольшим значением из двух (для сохранения структуры кучи после обмена). Когда узлы поменялись местами, вам нужно снова вызвать метод, чтобы увидеть, нужно ли вам переместить узел index дальше вниз по дереву.

    ...
    int biggest = index;
    if(leftChild < currentSize && heapArray[leftChild].getKey() > heapArray[index].getKey())
        biggest = leftChild;  //LeftChild is bigger
    if(rightChild < currentSize && heapArray[rightChild].getKey() > heapArray[biggest].getKey())
        biggest = rightChild; //RightChild is bigger than both leftChild and the index node

    if(biggest != index) //If a swap is needed
    {
        //Swap
        Node swapper = heapArray[biggest];
        heapArray[biggest] = heapArray[index];
        heapArray[index] = swapper;

        restoreHeap(biggest);
    }
}
person MAV    schedule 29.03.2013
comment
Большое спасибо. Это было очень полезно! - person Rishad Bharucha; 04.04.2013