Heap implementation of priority queue?

Question

I'm trying to implement a queue of patients using a heap (with root smaller than children) but when I print the queue, the queue of patients doesn't look prioritized.

Insertion method works fine but it's the enqueue that doesn't prioritize items?

// 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; }

Maybe you should post your reorder and expand methods. You current peace of code is not related to your problem. — Marcinek
– Marcinek, Commented Nov 25, 2015 at 7:40
Print it how? Unless you successively remove the first item and print it, you won't get an ordered listing. The heap array itself isn't sequential. — user207421
– user207421, Commented Nov 25, 2015 at 7:56
this is how i print: public void display(Heap h){ for(int i=0;i<h.count;i++) System.out.println(heapArray[i]); } — Square-root
– Square-root, Commented Nov 25, 2015 at 8:13
a@EJP are you saying i have to remove 1st item before printing the array? — Square-root
– Square-root, Commented Nov 25, 2015 at 8:23
Why are you substracting 1 to variable nextin the reorder() method in the sentence int next = count -1;? and also when you swap items it seems that you swap with the element in position (N-1)/2 I guess you have to do it with the element at N/2. Just a guess anyway — sir psycho sexy
– sir psycho sexy, Commented Nov 25, 2015 at 8:24

user207421 · Accepted Answer · 2015-11-25 08:44:03Z

2

This is how I print:

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

Wrong.

Unless you successively remove the first item and print it, you won't get an ordered listing. The heap array itself isn't sequential.

answered Nov 25, 2015 at 8:44

user207421

312k45 gold badges324 silver badges493 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Square-root Over a year ago

thing is heap uses patient id to order so what u suggested will print id in order. but i want to print priority in order: e.g 1 2 3 4

user207421 Over a year ago

I understand that you want to print it in order, and that's what my answer tells you how to do. You don't seem to understand how priority heaps actually work. They aren't sorted arrays; they are essentially partially-sorted binary trees. The first thing you need to do is implement a dequeue() method as @virtualagent07 suggested.

Square-root Over a year ago

i have dequeue. it just removes the root. i'll try again

user207421 Over a year ago

It only has to remove the root and re-establish the heap invariant. Do you understand what 'successively remove and print' means?

Square-root Over a year ago

i guess so but my dequeue and removerootitem both work fine.

|

user207421 · Accepted Answer · 2015-11-25 08:55:28Z

Shouldn't the last line of reorder method be part of the while loop?

heapArray[next] = temp;

Also, there should be proper dequeue() method out there

Collectives™ on Stack Overflow

Heap implementation of priority queue?

2 Answers 2

6 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Related