?
Solved

Heap using 3 arrays (coursework)

Posted on 2011-04-22
8
Medium Priority
?
333 Views
Last Modified: 2013-11-13
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.
0
Comment
Question by:TheBigB11
5 Comments
 
LVL 1

Expert Comment

by:taggarwal_expert
ID: 35457709
can you please explain the problem statement a bit more? Stress mainly of function parameters, their usage. if possible explain with an example....
0
 
LVL 92

Expert Comment

by:objects
ID: 35464050
0
 
LVL 32

Accepted Solution

by:
phoffric earned 2000 total points
ID: 35464813
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
 
LVL 32

Expert Comment

by:phoffric
ID: 35821569
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
 
LVL 53

Expert Comment

by:Dhaest
ID: 35909922
This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will show how Aten was able to supply easy management and control for Artear's video walls and wide range display configurations of their newsroom.
If you are a mobile app developer and especially develop hybrid mobile apps then these 4 mistakes you must avoid for hybrid app development to be the more genuine app developer.
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
Screencast - Getting to Know the Pipeline
Suggested Courses
Course of the Month16 days, 14 hours left to enroll

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question