Heap using 3 arrays (coursework)

I am new to programming and my teacher wants us to implement a priority queue using heap with 3 arrays. instance variables (data[], priority[],entered[]). How would I go about doing this? I only need an add and remove method.
TheBigB11Asked:
Who is Participating?
 
phoffricConnect With a Mentor Commented:
I assume that you know the max number of elements in your PQ and that you will pass this number into the PQ constructor. You didn't specify whether the top of the heap is a max or min priority. You can implement your PQ as a binary heap.

data[k], priority[k] represent the k-th node, and these do not have to be moved about.

entered[m] refers to the m-th element in the binary heap. When m is 0, then you are talking about the top of the heap (or PQ). Suppose entered[0] is 5. That would mean that the data/priority of the top node is data[5], priority[5].

This can get a bit messy, so be careful. Notice that to get the value of the data and priority of the m-th element in the heap array requires an index of entered[m] leading to:
data[ entered[m] ]
priority [ entered[m] ]

What you have is a binary heap where each element in the heap has up to two children. When you add a node to your PQ, you insert it at the end of the heap array, and then let it sift up by consecutive comparisons.

If the index of the element you are considering is idx, then the indexes of the left and right child, respectively, are:
Left_idx   = 2 * idx
Right_idx = 2 * idx + 1

The add and remove operations are described here nicely with useful pictures showing the steps:
     http://en.wikipedia.org/wiki/Binary_heap#Heap_operations
0
 
taggarwal_expertCommented:
can you please explain the problem statement a bit more? Stress mainly of function parameters, their usage. if possible explain with an example....
0
 
objectsCommented:
0
 
phoffricCommented:
Author asks for a very specific design of a priority queue:
heap
3 arrays named data[], priority[], and entered[]
In http:#35464813 are definitions and relationships of these three arrays. Also, since the heap is to be implemented as an array, this post also provides the parent/child index relationships for the heap. The add and remove operations for the Priority Queue are explained in a provided link.
0
 
DhaestCommented:
This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.