Как реализовать PriorityQueue без использования класса Java?

Question

Я пытаюсь создать PriorityQueue без использования класса PriorityQueue, предоставляемого Java. Для этого у меня есть некоторые методы, которые я должен заполнить. Я не уверен, где я делаю ошибку. Кажется, что мои функции put и get неверны, и я не уверен, как сделать новый PQ, как указано в коде. У меня есть следующее:

class Element {

private int priority;
private String data;

Element(int priority, String data) { 
    // Ihr Code
    this.priority = priority;
    this.data = data;

 }

public String getData() { 
    // Ihr Code
    return data;
}


public int getPriority() { 
    // Ihr Code
    return priority;
 }

/**
 * Return data and priority as string 
 * Format: Data (Priority)
 * e.g: abc (7)
 */
public String toString()        {
    String str = data + " " + Integer.toString(priority) + ")";  
    return str;
}
}


public class PriorityQueue {


static final int SIZE = 32;


private Element[] data = null;

// actual number of entries
private int len = 0;


/**
 * Creates a new PriorityQueue
 */
public PriorityQueue() {
    // Ihr Code      
}

/** 
 * Adds a new element into the queue as long as there is space
 * Returns true if element could be added, otherwise false 
 */
boolean put(Element element) {
    // Ihr Code
    if(len == SIZE){
        return false;
    }else{
        int i = len-1;
        while (i>=0 && element.getPriority() > data[i].getPriority()){
            data[i+1] = data[i];
            i--;
        }
        data[i+1] = element;
        len++;
        return true;
    }

}

/**
 * Returns element with the highest priority 
 * and removes it from the queue. Otherwise returns null
 * 
 */
Element get() {
    // Ihr Code
    if (len > 0){
        Element x = q[0];
        for(int i = 1; i < len; i++){
            data[i-1] = data[i];
        }
        len--;
        return x;
        }else{
             return null;
        }
    }

/**
 * Number of entries 
 */
int length() {
    // Ihr Code
    return len;
 }

/**
 * Returns contents of the queue as a String
 * Format: data1 (priority1), data2 (priority2)
 * e.g: abc (7), cde (8)
 * Attention: There should be no comma at the end of the String 
 */
public String toString() {
    //  Code
    String res = new String();
    //res = "(" + data + "," + ")";

    if(data.length>0){
        StringBuilder sb = new StringBuilder();

        for(String s: data){
            sb.append(s).append(",");
        }
        res = sb.deleteCharAt(sb.length()-1).toString;
    }

    return res;
 }

Я также борюсь с последним методом toString, чтобы вернуть очередь в виде строки в указанном формате, я пытался что-то с StringBuilder, но это не 'правильно скомпилировать. В качестве альтернативы, я мог бы сделать это с помощью обычного цикла for, но опять же я борюсь с точным синтаксисом.

Я нашел ресурсы в сети для создания этого PQ со структурами кучи (чего у меня еще не было) и с классом под названием Comparator, который я не смог понять. Любая помощь будет высоко ценится!

Я в основном борюсь с функцией

public PriorityQueue(){
      //what code?}

. Как я должен сделать "новый" PQ здесь? Это должно быть

PriorityQueue pq = new PriorityQueue(); 

Я совершенно заблудился! Большое спасибо за помощь.

Answer 1

Конструктор просто должен инициализировать Element[]:

public PriorityQueue() {
    data = new Element[SIZE];
}

Теперь put(). Этот метод создает ArrayOutOfBoundsException в цикле while, поскольку вы начинаете с i = len - 1, которое является последним полем data. Затем вы получаете доступ к data[i+1], который не существует, и будет выдано исключение (если, конечно, вы не инициализируете его с data = new Element[SIZE + 1]).

Решение: просто используйте i и i-1:

boolean put(Element element) {
    if (len == SIZE) {
        return false;
    } else {
        // EDIT: I changed i = len - 1 to i = len since, otherwise,
        // the last element would always be overwritten. Now, the
        // last element gets copied to the first "free" element and
        // so on.
        i = len;
        while (i > 0 && element.getPriority() > data[i-1].getPriority()) {
            data[i] = data[i - 1];
            i--;
        }
        data[i] = element;
        len++;
        return true;
    }
}

РЕДАКТИРОВАТЬ: Я уже говорил, что будет возвращен элемент с наименьшим приоритетом. На самом деле, это наибольший .

Метод get() ведет себя так, как ожидалось (за исключением того, что он должен сказать Element x = data[0] вместо q[0] в начале). Он возвращает первый элемент массива (тот, который имеет наибольшее значение getPriority()) и перемещает остальные на один индекс вниз. Однако, если вы хотите, чтобы элемент с наименьшим значением был возвращен, просто переключите > на < в цикле while метода put():

while (i > 0 && element.getPriority() < data[i-1].getPriority()) {
    ...
}

И, наконец, метод toString(). Это выглядит в основном правильно, за исключением цикла for-each. Этот всегда выполняет итерацию по всему массиву , где он должен повторяться только до data[len - 1]. Итак, просто используйте вместо этого индекс, и у вас все будет хорошо:

public String toString() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append(data[i]).append(",");
    }
    if (sb.length() > 0) {
        sb.deleteCharAt(sb.length() - 1);
    }

    return sb.toString();
}

В качестве альтернативы, если у вас установлена ​​хотя бы Java 8, вы можете использовать потоки для этого метода:

public String toString() {
    return Arrays.asList(data).stream()
        .limit(len)
        .map(Element::toString)
        .collect(Collectors.joining(","));
}

Answer 2

Ваш конструктор PriorityQueue должен инициализировать массив и установить текущее количество элементов. То есть:

public PriorityQueue() {
    data = /* initialize array */
    len = 0;
}

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

public put(Element e) {
    if (len == SIZE) {
        return false;
    }
    data[len++] = e;
    return true;
}

И тогда ваш метод get ищет в массиве элемент с наивысшим приоритетом, сохраняет его, заменяет его наэлемент в конце массива и возвращает:

Element get() {
    if (len == 0) {
        return null;
    }
    int p = 0;
    for (int i = 1; i < len; ++i) {
        if (data[i].getPriority() < data[p].getPriority()]) {
            p = i;
        }
    }
    Element e = data[p];
    // replace with the last item
    data[p] = data[len-1];
    --len;
    return e;
}

Итак, put - это операция O (1), а get - это O (n). В вашем коде оба O (n).