Heap using 3 arrays (coursework)

Posted on 2011-04-22
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.
Question by:TheBigB11
    LVL 1

    Expert Comment

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

    Expert Comment

    LVL 31

    Accepted Solution

    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:
    LVL 31

    Expert Comment

    Author asks for a very specific design of a priority queue:
    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.
    LVL 53

    Expert Comment

    This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.

    Featured Post

    How to run any project with ease

    Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
    - Combine task lists, docs, spreadsheets, and chat in one
    - View and edit from mobile/offline
    - Cut down on emails

    Join & Write a Comment

    Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
    In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
    Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:
    This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

    755 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

    Need Help in Real-Time?

    Connect with top rated Experts

    16 Experts available now in Live!

    Get 1:1 Help Now