Вставить элемент в приоритетную очередь с атрибутом priority - PullRequest
Новая
       29

Вставить элемент в приоритетную очередь с атрибутом priority

0 голосов
/ 25 мая 2018

У меня есть упражнение, в котором я должен реализовать приоритетную очередь, используя min-heap.Однако я не могу использовать библиотеку PriorityClass, я должен сам ее реализовать.Мне уже удалось это сделать, но мой профессор сказал мне, что мои методы вставки неверны.Он сказал мне, чтобы создать класс Element, который содержит 2 атрибута типа T. Этими двумя атрибутами являются (элемент T и приоритет T).Как я могу отредактировать метод вставки? 

package priorityQueue;
import java.util.ArrayList;
import java.util.Comparator;
import priorityQueueInterfaces.PriorityQueue;


public class BinaryHeap<T> implements PriorityQueue<T> 
{
private int currentSize = 0;
private static final int DEFAULT_CAPACITY = 20;
private ArrayList<T> array = null;
private Comparator <? super T> comparator = null;

/**
 * Constructor of binary-heap
 */
public BinaryHeap(Comparator <? super T> comparator)
{
    currentSize = 0;
    array = new ArrayList<>(DEFAULT_CAPACITY + 1);
    this.comparator = comparator;
}

/**
 * Construct the binary heap from an arrayList
 */
public BinaryHeap(ArrayList<T> array, Comparator <? super T> comparator)
{
    this.currentSize = array.size();
    this.array = new ArrayList<>(array.size() + 1);
    this.comparator = comparator;

    for(int i = 0; i < array.size(); i++)
        this.array.set(i + 1, array.get(i));
}

/**
 * Method which builds the min heap with the minHeapify method
 * @throws PriorityQueueException
 */
public void buildMinHeap(ArrayList<T> array, int heapSize) throws PriorityQueueException
{
    for(int i = this.currentSize / 2; i > 0;i--)
        minHeapify(this.array,i,this.currentSize);
}

/**
 * Method which builds the max heap with the maxHeapify method
 * @throws PriorityQueueException
 */
public void buildMaxHeap() throws PriorityQueueException 
{
    for(int i = this.currentSize/2; i > 0; i--)
        maxHeapify(this.array,i,this.currentSize);
}

public void buildMaxHeap(ArrayList<T> array, int heapSize)throws PriorityQueueException
{
    if(this.array == null)
        throw new NullPointerException("ArrayList is null");
    if(this.array.size() <= 0 || heapSize <= 0 )
        throw new IllegalArgumentException("Illegal Parameters: either the arraylist or the heap size are not valid");
    if(heapSize > this.array.size())
        heapSize = this.array.size();

    for(int i = heapSize/2; i > 0; i--)
        maxHeapify(this.array,i,heapSize);
}

/**
 * Insert into the priority queue.
 * Duplicates are allowed.
 * @param element is the item to insert.
 */
public void insert(T element) throws PriorityQueueException 
{
    if(element == null)
        throw new IllegalArgumentException("Element to be inserted, cannot be null!");
    if(this.size() + 1 == this.array.size())
        extendArray();

    this.currentSize = this.size() + 1;

    if(this.isEmpty())
        this.array.add(0,element);
    else
    {
        this.array.add(element);
        int index = this.size() - 1;//indice index = all'elemento appena aggiunto

        while( index > 1 && this.comparator.compare(this.array.get(index/2), this.array.get(index)) < 0)
        {
            swapElements(index, index/2);
            index = index / 2;
        }
    }
}
/**
 * @param firstIndex of the element that has to be swapped
 * @param secondIndex of the element that has to be swapped
 * @throws PriorityQueueException
 */
private void swapElements(int firstIndex,int secondIndex)throws PriorityQueueException
{
    T temp = this.array.get(firstIndex);
    this.array.set(firstIndex, this.array.get(secondIndex));
    this.array.set(secondIndex,temp);
}
}

ЭТО МОЙ ЭЛЕМЕНТ КЛАСС , который я должен использовать для добавления элемента с минимальным приоритетом 

package priorityQueue;

public class Element<T> 
{
private T element;
private T priority;

public Element(T element,T priority)
{
    this.element = element;
    this.priority = priority;
}

public void setElement(T element)
{
    this.element = element;
}

public void setPriority(T priority)
{
    this.priority = priority;
}

public T getElement()
{
    return this.element;
}

public T getPriority()
{
    return this.priority;
}
}

Мой метод вставки работает очень хорошо, но я должен также вставить приоритет, содержащийся в элементе класса.Как это сделать?

...