java - 插入已排序的数组队列

Question

我正在研究排序队列，例如优先级队列。我已经用列表做到了，而且效果很好。现在我想用数组来做。但我在添加新元素并将其插入已排序数组时遇到了一些逻辑问题。

最终输出应该是这样的:
优先级:5 值:x
优先级:4 值:iso
....(等等)
因此优先级最高的元素应该位于索引 = 0 上。
我只是不知道(是的，我知道切换它真的很简单，但我就是做不到:/)如何做到这一点...

我已经尝试了一些方法，但我陷入困境......:/可以请任何人帮忙吗？

这是我的代码:

public class Queue {

private QueueElem[] a;

public Queue(int capacity) 
{
    QueueElem[] tempQueue = new QueueElem[capacity];
    a= tempQueue;
}

public void enqueue(int p, String v) 
{
    QueueElem neu = new QueueElem(p,v);
    int i=0;

        while(i<a.length) 
        {
            if (a[i] == null) 
            {
                a[i] = neu;
                break;
            }   
            i++;
        }
}

public void writeQueue()
{
    int i=0;
    while((i< a.length) && (a[i] != null))
    {
        System.out.println("Priority: " + a[i].priority + " Value: " + a[i].value);
        i++;
    }
}

public static void main(String args[])
{
    Queue neu = new Queue(10);
    neu.enqueue(4,"iso");
    neu.enqueue(2,"abc");
    neu.enqueue(5,"x");
    neu.enqueue(1,"abc");
    neu.enqueue(4,"bap");
    neu.enqueue(2,"xvf");
    neu.enqueue(4,"buep");  
}
 }//end class Queue


class QueueElem {
int priority;
String value = new String();

public QueueElem(){ }

public QueueElem(int p, String v)
{
    this.priority = p;
    this.value = v;
}

public int getPrio()
{
    return this.priority;
}

public String getValue()
{
    return this.value;
}   
}

Answer 1

如果将数组解释为最大堆，那就更好了。这是优先级队列的典型实现方式。

如果您尝试为优先级队列维护一个排序数组，您所需要的就是实现 insertion sort (某种程度上；您没有一个未排序的数组开始。您有一个空数组，只需添加即可，同时保持排序顺序)。每次插入一个新元素时，您都会遍历数组以找到正确的位置，然后将其插入那里，然后将当前位于该位置的元素以及该位置之后的所有元素向下移动一个位置。请注意，这不如使用堆实现的性能好，因为在最坏的情况下，每次插入时都会有 O(n) 性能，而使用堆则有 O(logn).