Куча реализации приоритетной очереди?

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

Метод вставки работает нормально, но enqueue не отдает приоритет элементам?

// Heap class
.....some code

//insertion: inserts patients into minimum heap using an array.
//expand array as needed and reorder heap to maintain its properties

public void insert(ER_Patient patient) {
    if(heapArray.length==count)
        expand();
    heapArray[count] = patient;
    count++;
    if(count>1)
        reorder();
}

// Priority Queue class
.......some code

public void enqueue(ER_Patient patient) {
    try {
        heap.insert(patient);
    } catch (NoSuchCategoryException exception) {
        System.out.println("Can't enqueue");
    }

}

// copy content of original's array to a new larger array
private void expand(){
    ER_Patient[] tempArray = new ER_Patient[heapArray.length * 8];
    for(int i=0;i<=heapArray.length-1;i++)
        tempArray[i]=heapArray[i];
    heapArray = tempArray;
}

// maintain heap property by keeping roots smaller than children
private void reorder(){
    ER_Patient temp;
    int next = count -1;
    temp = heapArray[next];
    while((next!=0) && temp.compareTo(heapArray[(next-1)/2])<0){
        heapArray[next] = heapArray[(next-1)/2];
        next = (next-1)/2;
    }
    heapArray[next] = temp;
}

person Square-root    schedule 25.11.2015    source источник
comment
Возможно, вам следует опубликовать свой повторный заказ и расширить методы. Ваш текущий мир кода не связан с вашей проблемой.   -  person Marcinek    schedule 25.11.2015
comment
Распечатать как? Если вы последовательно не удалите первый элемент и не распечатаете его, вы не получите упорядоченный список. Сам массив кучи не является последовательным.   -  person user207421    schedule 25.11.2015
comment
вот как я печатаю: public void display(Heap h){ for(int i=0;i‹h.count;i++) System.out.println(heapArray[i]); }   -  person Square-root    schedule 25.11.2015
comment
a@EJP, вы говорите, что мне нужно удалить 1-й элемент перед печатью массива?   -  person Square-root    schedule 25.11.2015
comment
Почему вы вычитаете 1 из переменной next в методе reorder() в предложении int next = count -1;? а также, когда вы меняете элементы, кажется, что вы меняетесь с элементом в позиции (N-1)/2. Я думаю, вам нужно сделать это с элементом в позиции N/2. Просто предположение в любом случае   -  person sir psycho sexy    schedule 25.11.2015
comment
@Square-root, что означает EJP, это структура, имеющая только частичный порядок, это идея двоичной кучи. Если вы хотите, чтобы все элементы, которые вы добавили в структуру, вернулись, вы должны удалить их все.   -  person sir psycho sexy    schedule 25.11.2015
comment
Обычно PriorityQueue (как в JDK) имеет самый низкий элемент первым. Однако это не гарантирует порядок любого другого элемента.   -  person Peter Lawrey    schedule 25.11.2015
comment
Какую часть «последовательно удалить первый элемент и распечатать» вы не понимаете?   -  person user207421    schedule 25.11.2015


Ответы (2)


Вот как я печатаю:

public void display(Heap h)
{
    for(int i=0;i<h.count;i++)
        System.out.println(heapArray[i]);
}

Неправильный.

Если вы последовательно не удалите первый элемент и не распечатаете его, вы не получите упорядоченный список. Сам массив кучи не является последовательным.

person user207421    schedule 25.11.2015
comment
Дело в том, что куча использует идентификатор пациента для заказа, поэтому то, что вы предложили, будет печатать идентификатор по порядку. но я хочу напечатать приоритет по порядку: например, 1 2 3 4 - person Square-root; 25.11.2015
comment
Я понимаю, что вы хотите напечатать его по порядку, и мой ответ говорит вам, как это сделать. Вы, кажется, не понимаете, как на самом деле работают приоритетные кучи. Это не отсортированные массивы; по сути, это частично отсортированные бинарные деревья. Первое, что вам нужно сделать, это реализовать метод dequeue(), как предложил @virtualagent07. - person user207421; 25.11.2015
comment
у меня очередь. он просто удаляет корень. я попробую еще раз - person Square-root; 25.11.2015
comment
Нужно только удалить корень и восстановить инвариант кучи. Вы понимаете, что означает «последовательно удалить и распечатать»? - person user207421; 25.11.2015
comment
я думаю, да, но мой dequeue и removerootitem работают нормально. - person Square-root; 25.11.2015
comment
Таким образом, ваш пересмотренный метод печати, который последовательно удаляет и печатает, также должен работать нормально. В отличие от for(int i=0;i<h.count;i++). - person user207421; 25.11.2015

Разве последняя строка метода переупорядочивания не должна быть частью цикла while?

heapArray[next] = temp;

Кроме того, должен быть правильный метод dequeue().

person virtual agent 07    schedule 25.11.2015