java - 如何在不使用Java类的情况下实现PriorityQueue？

Question

我试图在不使用Java提供的PriorityQueue类的情况下创建一个PriorityQueue。为此，我有一些必须填写的给定方法。我不确定我在哪里犯了错误。看来我的 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 循环来实现它，但我再次在精确的语法上苦苦挣扎。

我在网上找到了使用堆结构(我还没有)和一个我无法理解的名为 Comparator 的类来构建这个 PQ 的资源。任何帮助将不胜感激!

我主要是在挣扎

public PriorityQueue(){
      //what code?}

功能。我该如何在这里创建一个"new"PQ？应该是这样吗

PriorityQueue pq = new PriorityQueue(); 

我彻底迷失了!非常感谢你的帮助。

Answer 1

您的 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)。