Биномиальная приоритетная очередь Min-Heap с универсальными типами

В настоящее время я реализую биномиальную приоритетную очередь Min-Heap с универсальными типами.

Я дал следующий binomialminheap.java:

class BinomialMinHeap <K extends Comparable<? super K>, P>
{

    public static class Entry <K, P> {
        private P priority;
        private K key;
        private Node<P, K> node;

        private Entry (K k, P p)
        {
            priority = p;
            key= k;
        }

        public P priority () { return priority; }
        public K key() { return key; }
    }

    private static class Node <K, P> {

        private Entry<K, P> entry;

        private Node<K, P> parent;
    .
        private Node<K, P> child;

        private Node<K, P> sibling;

        private int degree;

        private Node (Entry<K, P> e)
        {
            entry = e;
            e.node = this;
        }

        private P priority ()
        {
            return entry.priority;
        }
    }
}

Как видите, у меня есть универсальные типы P и K. Проблема здесь в том, что я понятия не имею, как реализовать универсальные типы в моей двоичной куче. Как «вход», «узел» и «биномиальная куча» работают вместе?

Я начал со следующего конструктора и нескольких методов:

    private Node<P,D> Nodes;
    private int size;

    public BinomialMinHeap()
    {
        Nodes = null;
        size = 0;
    }

    public boolean isEmpty ()
    {
        return Nodes == null;
    }

    public int size()
    {
        return size;
    }

Я должен добавить следующие методы:

boolean contains (Entry<K, P> e)
Entry<K, P> insert (K k, P p)
boolean changePriority (Entry<K, P> e, P p)
Entry<K, P> minimum ()
Entry<K, P> extractMinimum ()
boolean remove (Entry<K, P> e)

person ThristBugz    schedule 14.12.2016    source источник


Ответы (1)


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

Сортировка кучей

Сортировка вставками

Сортировка выбором

Сортировка слиянием

Быстрая сортировка

person Hari Krishna    schedule 14.12.2016