Sign in to follow this  

maxheap based priority queue

This topic is 3871 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hey guys im really having a problem with implementing this maxheap for a priority queue(in java)...i cant figure out the insert and remove functions ive already tried a bunch of things..i'll include what i have besides those functions. also one question about the print function, since its supposed to be for a priority queue would i print out the array just like it is or would i print it out like list[i], list[2i], list[2i+1] thanks for your help.
public class MaxHeap
{
    private int[] elements;
    private int currSize;
    public MaxHeap()
    {
        elements = new int[25];
        currSize = 0;
    }
    public boolean isEmpty()
    {
        return(currSize == 0);
    }
    public boolean isFull()
    {
        return(currSize == 25);
    }

Share this post


Link to post
Share on other sites
Other than the insert and remove functions, the class is trivial. What have you done with those functions so far? What reference material are you using?

Share this post


Link to post
Share on other sites
First thing would be why would you want to print it out? From you asking which way then I would assume you don't fully understand that a heap only guarantees the value at the top and not the order of the rest.u
Insertion and removal are normally completed using the walk up and walk down algorithm's.
Insert/ walkup places the new node on the last level at the first free child.
It is then compared to its parent and if its larger is swapped.
continue until parent is greater than the node or node is the root.

remove/ walkdown
remove the top element and in its place insert the right most child on the last level.
if the node has a left and a right child check which is the largest
if this child is larger then the current node swap it.
continue until the node is greater than all of children or is on the last level(has not children)

Share this post


Link to post
Share on other sites

This topic is 3871 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this