Бинарные реализация "кучи" в Java


Вот мой массив на основе двоичной кучи Java-реализации, ищу комментарии / предложения на мой подход. Я использовал базовый класс кучи, чтобы содержать большую часть логики, так как поведение мин/макс кучи очень похожа. Я нашел массив на основе реализации достаточно простой, чтобы построить по сравнению с древовидных структур, только механика, я действительно могу думать, чтобы добавить в этот момент-это динамично-изменение размеров основного массива, вместо использования фиксированного размера только.

Основной куче абстрактный класс:

public abstract class Heap<T extends Comparable<T>> {

    protected T[] heap;
    protected final int maxSize;
    protected int size;

    public Heap(Class<T> clazz, int maxSize) {
        this.maxSize = maxSize;
        this.heap = (T[]) Array.newInstance(clazz, this.maxSize);
        this.size = 0;
    }

    /**
    * Inserts an element into the heap.
    * @param data item to insert.
    * @throws HeapException
    */
    public void insert(T data) throws HeapException {
        if(this.size >= this.maxSize) {
            throw new HeapException();
        }
        this.heap[this.size] = data;
        upHeap();
        this.size++;
    }

    /**
    * Returns the current extreme value within the heap.
    * @return object representing current extreme value.
    * @throws HeapException
    */
    public T getExtreme() throws HeapException {
        if(isEmpty()) {
            throw new HeapException();
        }
        return this.heap[0];
    }

    /**
    * Returns and removes the current extreme value from within the heap, replacing the old extreme with the next candidate.
    * @return object representing extreme value.
    * @throws HeapException
    */
    public T removeExtreme() throws HeapException {
        if(isEmpty()) {
            throw new HeapException();
        }
        T extreme = this.heap[0];
        this.heap[0] = this.heap[this.size - 1];
        this.heap[this.size - 1] = null;
        this.size--;
        downHeap();
        return extreme;
    }

    /**
    * 'Bubbles-up' an item from the bottom of the heap (tail of the array) into it's appropriate spot, following the rules of a Min Heap.
    */
    protected void upHeap() {
        int currentIndex = this.size;
        while(currentIndex > 0) {
            int parentIndex = (currentIndex % 2 == 0) ? (currentIndex / 2) - 1 : currentIndex / 2;
            if(upHeapComparator(currentIndex, parentIndex)) {
                break;
            }
            swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
        }
    }

    /**
    * Percolates-down an item from the top of the heap (head of the array) into it's appropriate spot, following the rules of the underlying heap class.
    */
    protected void downHeap() {
        int currentIndex = 0;
        while(true) {
            int leftChildIndex = (2 * currentIndex) + 1;
            int rightChildIndex = (2 * currentIndex) + 2;
            if(leftChildIndex < this.size && rightChildIndex < this.size) {
                int extremeIndex = findExtremeIndex(leftChildIndex, rightChildIndex);
                if(downHeapComparator(currentIndex, extremeIndex)){
                    swap(currentIndex, extremeIndex);
                    currentIndex = extremeIndex;
                } else {
                    break;
                }
            }
            else if(leftChildIndex < this.size) {
                if(downHeapComparator(currentIndex, leftChildIndex)) {
                    swap(currentIndex, leftChildIndex);
                    currentIndex = leftChildIndex;
                } else {
                    break;
                }
            }
            else {
                break;
            }
        }
    }

    /**
    * Comparison method used with up-heap operations, to be overridden within inheriting class.
    * @param xIndex first index to use within comparison.
    * @param yIndex second index to use within comparison.
    * @return true or false based on the inheriting class' implementation.
    */
    protected abstract boolean upHeapComparator(int xIndex, int yIndex);

    /**
    * Comparison method used with down-heap operations, to be overridden within inheriting class.
    * @param xIndex first index to use within comparison.
    * @param yIndex second index to use within comparison.
    * @return true or false based on the inheriting class' implementation.
    */
    protected abstract boolean downHeapComparator(int xIndex, int yIndex);

    /**
    * Comparison method used when finding an extreme value, to be overridden within inheriting class.
    * @param xIndex first index to use within comparison.
    * @param yIndex second index to use within comparison.
    * @return true or false based on the inheriting class' implementation.
    */
    protected abstract boolean extremeComparator(int xIndex, int yIndex);

    /**
    * Compares two values within the underlying heap array and returns the index of the maximum.
    * @param xIndex index of first item to use in comparison.
    * @param yIndex index of second item to use in comparison.
    * @return integer representing index of the maximum value from the comparison.
    * @throws IndexOutOfBoundsException
    */
    protected int findExtremeIndex(int xIndex, int yIndex) throws IndexOutOfBoundsException {
        if(xIndex >= this.size || yIndex >= this.size) {
            throw new IndexOutOfBoundsException();
        }
        return (extremeComparator(xIndex, yIndex)) ? xIndex : yIndex;
    }

    /**
    * Quick method used to swap two items within the underlying heap array.
    * @param xIndex index of first item to swap.
    * @param yIndex index of second item to swap.
    * @throws IndexOutOfBoundsException
    */
    protected void swap(int xIndex, int yIndex) throws IndexOutOfBoundsException {
        if(xIndex > this.size || yIndex > this.size) {
            throw new IndexOutOfBoundsException();
        }
        T temp = this.heap[xIndex];
        this.heap[xIndex] = this.heap[yIndex];
        this.heap[yIndex] = temp;
    }

    /**
    * Compares two values.
    * @param x first value to use in comparison.
    * @param y second value to use in comparison.
    * @return
    */
    protected int compare(T x, T y) {
        return x.compareTo(y);
    }

    /**
    * Returns the heap in array form.
    * @return array of generic objects representing the heap.
    */
    public T[] getHeap() {
        return this.heap;
    }

    /**
    * Returns the allotted maximum size of the underlying heap array.
    * @return an integer representing maximum size of the heap.
    */
    public int getMaxSize() {
        return this.maxSize;
    }

    /**
    * Returns the current number of elements present within the underlying heap array.
    * @return an integer representing the current number of elements within the heap.
    */
    public int getSize() {
        return this.size;
    }

    /**
    * Determines whether or not the heap contains any elements.
    * @return true if the heap is empty, false if otherwise.
    */
    public boolean isEmpty() {
        return this.size <= 0;
    }

}

Мин-кучи реализацию, расширяя базовый класс кучи:

public class MinHeap<T extends Comparable<T>> extends Heap<T> {

    public MinHeap(Class<T> clazz, int maxSize) {
        super(clazz, maxSize);
    }

    @Override
    protected boolean upHeapComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) >= 0;
    }

    @Override
    protected boolean downHeapComparator(int xIndex, int yIndex) {
        return compare(this.heap[xIndex], this.heap[yIndex]) > 0;
    }

    @Override
    protected boolean extremeComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) <= 0;
    }

}

Макс-кучи реализацию, расширяя базовый класс кучи:

public class MaxHeap<T extends Comparable<T>> extends Heap<T> {

    public MaxHeap(Class<T> clazz, int maxSize) {
        super(clazz, maxSize);
    }

    @Override
    protected boolean upHeapComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) < 0;
    }

    @Override
    protected boolean downHeapComparator(int xIndex, int yIndex) {
        return compare(this.heap[xIndex], this.heap[yIndex]) <= 0;
    }

    @Override
    protected boolean extremeComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) > 0;
    }

}

Дополнительный класс HeapException:

public class HeapException extends Exception {

    public HeapException() {
        super();
    }

    public HeapException(String message) {
        super(message);
    }
}


995
3
задан 2 февраля 2018 в 04:02 Источник Поделиться
Комментарии
2 ответа


        while(true) {
int leftChildIndex = (2 * currentIndex) + 1;
int rightChildIndex = (2 * currentIndex) + 2;
if(leftChildIndex < this.size && rightChildIndex < this.size) {
int extremeIndex = findExtremeIndex(leftChildIndex, rightChildIndex);
if(downHeapComparator(currentIndex, extremeIndex)){
swap(currentIndex, extremeIndex);
currentIndex = extremeIndex;
} else {
break;
}
}
else if(leftChildIndex < this.size) {
if(downHeapComparator(currentIndex, leftChildIndex)) {
swap(currentIndex, leftChildIndex);
currentIndex = leftChildIndex;
} else {
break;
}
}
else {
break;
}
}

Вы могли бы избавиться от повторяющегося кода с чем-то подобным

        for (int left = (2 * currentIndex) + 1; left < size; left = (2 * currentIndex) + 1) {
int right = left + 1;
int extreme = right < size ? findExtremeIndex(left, right) : left;

if (!downHeapComparator(currentIndex, extreme)) {
return;
}

swap(currentIndex, extreme);
currentIndex = extreme;
}

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

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

В Java, вам только нужно использовать this. для устранения неоднозначности. Вы можете использовать его, чтобы указать, какие переменные поля объекта, но вам не нужно этого делать. Это ваш выбор. Я выбираю не использовать его, когда мне не нужно делать так.

Я предпочитаю, чтобы положить пространство между структурой управления ключевые слова while, forили if и скобочки после них. Это помогает отделить их от вызовов методов, как swap.

Я получил в привычку ломать или вернуться на негативное состояние. Тогда мне не придется использовать дополнительный отступ на позитивное состояние.

Я не уверен, что ваш upHeapComparator и downHeapComparator должны быть логические противоположности. В частности, я думаю, что вам стоит только swap когда не равны. При равной, она должна быть пустой.

2
ответ дан 2 февраля 2018 в 05:02 Источник Поделиться

Это хороший код, но я еще добавлю пару советов. Некоторые из них могут быть субъективными, но если он добавляет никакой ценности, его, вероятно, стоит.


  1. Я чувствовал, в двух форматах this.heap[xIndex].compareTo(this.heap[yIndex]) < 0; и compare(this.heap[xIndex], this.heap[yIndex]) <= 0; запутанным. Я понимаю всю концепцию сухих и прочее, но взять его с горсть соли. Сделать его использовать тот же формат.

  2. Как правильно отметил @mdfs13, while(true) может и должен быть заменен.

  3. Профессионально, куча может быть расширяемой, не ограничен фиксированным размером.

  4. Каждый раз, когда вы бросаете HeapExceptionвы передаете его пустым, т. е. без какого-либо строку сообщения.

  5. Ваш ребенок занятия upHeapComparator(int xIndex, int yIndex)это может быть опасным, так как xIndex предполагается child и yindex должен быть parent.

  6. Ваш getHeap должны вернуть неизменными array.

  7. С учетом вашей реализации, вы не должны сталкиваться if(xIndex >= this.size || yIndex >= this.size) { это условие в findExtremeIndex. Хорошо иметь проверить, но вы можете избежать подобных проверок в частных методов, так как они находятся под вашим контролем.

  8. В isEmpty эта проверка this.size == 0 следует enof. Не нужно проверять this.size <= 0;

  9. Вы можете заявить об этом final тоже. protected final T[] heap;

1
ответ дан 2 февраля 2018 в 09:02 Источник Поделиться