Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: regarding min-PQ

  1. #1
    Member
    Join Date
    May 2011
    Posts
    61
    My Mood
    Busy
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default regarding min-PQ

    Hi, I read heaps are efficient to build a min-PQ and in turn to use an array to make a min-heap. THe problem is if I print the list, it's not truly items in a min-PQ for example:

    I could have a heap of: 3,6,7,15,16,8
    so represented as a binary tree:
    3
    6 7
    15 16 8

    So as a heap, all node's are less than its children, but once I print the array: 3,6,7,15,16,8, It should be: 3,6,7,8,15,16. Why is this point never brought up whenever I heart efficiency of a heap to build a PQ (max or min PQ)? What should I do to ensure it's in ascending order, should heap sort be the best way


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: regarding min-PQ

    First, by PQ I presume you mean Priority Queue - for future reference you should be a lot more explicit when posting.

    So as a heap, all node's are less than its children, but once I print the array: 3,6,7,15,16,8, It should be: 3,6,7,8,15,16. Why is this point never brought up whenever I heart efficiency of a heap to build a PQ (max or min PQ)?
    A heap satisfies the heap property - which defines the relationship between parent and child, there is nothing within this property that suggests sibling order. Hence represented within an array a heap may not be a sorted array. A heap as a priority queue is efficient given its log(n) complexity for inserts and deletes.

    What should I do to ensure it's in ascending order, should heap sort be the best way
    What is the goal? If it is to sort an array, then sort the array (which begs the question why you want a priority queue implemented as a heap when your goal is to fully sort)

Similar Threads

  1. [SOLVED] Help with Min Heap Implementation (with an array)
    By arsparfven in forum What's Wrong With My Code?
    Replies: 10
    Last Post: April 27th, 2012, 05:57 AM
  2. Multi-D array. daily max/min/avg, weekly max/min/avg, sum total (99% done)
    By TheWhopper858 in forum Collections and Generics
    Replies: 1
    Last Post: November 6th, 2011, 08:50 PM
  3. Need help with C++ min and max heaps.
    By javapenguin in forum Other Programming Languages
    Replies: 6
    Last Post: October 19th, 2011, 11:08 AM
  4. Finding min in linked list
    By lieles in forum What's Wrong With My Code?
    Replies: 1
    Last Post: February 7th, 2011, 02:06 AM
  5. DUE IN 10 min
    By iank in forum File I/O & Other I/O Streams
    Replies: 0
    Last Post: November 5th, 2009, 02:54 PM