.
 Vyom World.com  . Let's Touch the Sky Together!  
.
. . . . . . .
 Home
VyomWorld.com Home
Free Magazines!
VyomLinks.com Home
JobsAssist.com Home
Vyom Network
Contact Us
 Jobs & Careers
Resume Submitter
Placement Papers
IT Companies Directory
Computer Jobs
Interview Questions
Online Exams
Vyom Career eMag.
 Fun
Screensavers New!
Send FREE SMS!
SMS Jokes
 Source Codes Library
Source Codes Home
ASP Source Codes
C Source Codes
C++ Source Codes
COBOL Source Codes
Java Source Codes
Pascal Source Codes
Submit Source Codes
 GATE
GATE an Overview
GATE Preparation
Study Materal
 GRE
GRE an Overview
GRE Questions
GRE Preparation
GRE Universities
 TOEFL Preparation
TOEFL Resources
 GMAT Preparation
GMAT Resources
 MBA Preparation
MBA Resources
 Networking Concepts
Networking Concepts
 Testing Preparation
Testing Resources
 Webmasters
Free Traffic Builder
Webmaster Articles
Web Hosting
 Tutorials
Hardware Tutorial
1500 Free eBooks New!
 FREE Publications
Vyom Career eMag.
 
.
Get 9,000+ Interview Questions & Answers in an eBook.


  • 9,000+ Interview Questions
  • All Questions Answered
  • 5 FREE Bonuses
  • Free Upgrades

    Get it now!


    Post your Resume to 5800+ Companies

    Reliable Web Hosting

  •  
     
     
    Get 9,000+ Interview Questions with Answers in an eBook


     Home

    Analysis and Design of Algorithms


    Advertisements
    Advertisements

    7.4 Heaps and Heap sort:

    A heap is a complete binary tree with the property that the value at each node is atleast as large as the value at its children.

    The definition of a max heap implies that one of the largest elements is at the root of the heap. If the elements are distinct then the root contains the largest item. A max heap can be implemented using an array an[ ].

    To insert an element into the heap, one adds it "at the bottom" of the heap and then compares it with its parent, grandparent, great grandparent and so on, until it is less than or equal to one of these values. Algorithm insert describes this process in detail.





    Algorithm Insert(a,n)

    {

    // Insert a[n] into the heap which is stored in a[1:n-1]

    I=n;

    item=a[n];

    while( (I>n) and (a[ I!/2 ] < item)) do

    {

    a[I] = a[I/2];

    I=I/2;

    }

    a[I]=item;

    return (true);

    }

     

     

    The figure shows one example of how insert would insert a new value into an existing heap of five elements. It is clear from the algorithm and the figure that the time for insert can vary. In the best case the new elements are correctly positioned initially and no new values need to be rearranged. In the worst case the number of executions of the while loop is proportional to the number of levels in the heap. Thus if there are n elements in the heap, inserting new elements takes O(log n) time in the worst case.

    To delete the maximum key from the max heap, we use an algorithm called Adjust. Adjust takes as input the array a[ ] and integer I and n. It regards a[1..n] as a complete binary tree. If the subtrees rooted at 2I and 2I+1 are max heaps, then adjust will rearrange elements of a[ ] such that the tree rooted at I is also a max heap. The maximum elements from the max heap a[1..n] can be deleted by deleting the root of the corresponding complete binary tree. The last element of the array, i.e. a[n], is copied to the root, and finally we call Adjust(a,1,n-1).

    Algorithm Adjust(a,I,n)

    {

    j=2I;

    item=a[I];

    while (j<=n) do

    {

    if ((j<=n) and (a[j]< a[j+1])) then

    j=j+1;

    //compare left and right child and let j be the right //child

    if ( item >= a[I]) then break;

    // a position for item is found

    a[i/2]=a[j];

    j=2I;

    }

    a[j/2]=item;

    }

    Algorithm Delmac(a,n,x)

    // Delete the maximum from the heap a[1..n] and store it in x

    {

    if (n=0) then

    {

    write(‘heap is empty");

    return (false);

    }

    x=a[1];

    a[1]=a[n];

    Adjust(a,1,n-1);

    Return(true);

    }

     

    Note that the worst case run time of adjust is also proportional to the height of the tree. Therefore if there are n elements in the heap, deleting the maximum can be done in O(log n) time.

    To sort n elements, it suffices to make n insertions followed by n deletions from a heap since insertion and deletion take O(log n) time each in the worst case this sorting algorithm has a complexity of

    O(n log n).

    Algorithm sort(a,n)

    {

    for i=1 to n do

    Insert(a,i);

    for i= n to 1 step –1 do

    {

    Delmax(a,i,x);

    a[i]=x;

    }

    }

     

    Study Notes Home | References>>




     

    Discussion Center

    Discuss

    Query

    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    .

    Recently Updated: New Placement Papers added.
    Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory

    Copyright ©2003-2018 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy