Вопрос:

Реализация MaxHeap в Java не работает должным образом

java algorithm heap

72 просмотра

1 ответ

68 Репутация автора

Я реализовал Heap, расширив ArrayList. Тем не менее, он, кажется, работает хорошо, как minheap (с небольшой разницей в этом коде), но он не работает должным образом, как maxheap. Я думаю, что у меня есть часть или часть, которую я использую неправильно. Интересно, что неправильно или неправильно понято.

И если есть лучший способ, я был бы очень признателен, если вы это прокомментируете, спасибо.

class Heap<T extends Comparable<T>> extends ArrayList<T>   {

    public void insert(T elem) {
        this.add(elem);
        int idx = this.size() - 1;
        if(idx > 0 && this.compare(idx, (idx - 1) / 2)){
            Collections.swap(this, idx, (idx - 1) / 2);
            idx = (idx - 1) / 2;
        }
    }
    public void removeTop() {
        if(this.size() == 1) {
            this.remove(0);
            return;
        }
        this.set(0, this.remove(this.size() - 1));
        int here = 0;
        while(true) {
            int left = here * 2 + 1;
            int right = here * 2 + 2;
            if(left >= this.size()) break;
            int next = here;
            if(!this.compare(next, left)) {
                next = left;
            }
            if(right < this.size() && !this.compare(next, right)){
                next = right;
            }
            if(next == here) break;
            Collections.swap(this, next, here);
            here = next;
        }
    }

    private void swap(int idx1, int idx2) {
        T temp = this.get(idx1);
        this.set(idx1, this.get(idx2));
        this.set(idx2, temp);
    }

    private boolean compare(int idx1, int idx2) {
        return this.get(idx1).compareTo(this.get(idx2)) >= 0;
    }
}

(+) Метод compareдля сравнения двух элементов в зависимости от типа. Я бы хотел получить вид Compare functionво время инициализации кучи. лайк...

Heap<Integer> heap = new Heap<Integer>(new SomekindofCompareFunction());

это возможно в Java?

Автор: Jason Park Источник Размещён: 02.01.2018 07:25

Ответы (1)


1 плюс

6163 Репутация автора

Решение

Используйте Comparator:

class Heap<T> extends ArrayList<T>   {
    private final Comparator<T> comparator;

    public Heap(Comparator<T> comparator) {
        this.comparator = comparator;
    }

...

    private boolean compare(int idx1, int idx2) {
        return comparator.compare(get(idx1), get(idx2)) >= 0;
    }
}

Вы бы создали Heapтак:

    Heap<Integer> heap = new Heap<Integer>((a,b) -> a.compareTo(b));
Автор: Maurice Perry Размещён: 02.01.2018 07:47
Вопросы из категории :
32x32