Saturday 18 July 2015

Heap Basics

Heap is also called Left Complete binary tree. i.e Binary tree with some of rightmost node removed.
It is very efficient for priority Queue implementation.
MaxHeap

Heap Type:

  1. Minimum Key Heap: Root node is always minimum.
  2. Maximum key Heap:  Root node is always maximum.

It can Easily Implement in array and It will be more easier to implement if we take 1th index of array as root of heap( leave 0th index of array ).
Then
  • Parent  of i'th Node is = [i/2] {it is flore of i//2}  
  • Left child of i'th Node is = 2*i
  • Right child of i'th Node = 2*i +1

Heapify(A,i) 

is a function that used to maintain heap property of left complete binary tree.
A <= Array 
i  <= Index of node that need rearrangement to satisfy make array A a heap.

This C++ Program Demonstrate use of Hepify 

  1. //Maxheap
  2. //Note this program first create complete binary tree then
  3. //hepify it . but it does not hepify after each insertion
  4. //but it can easily done by applying hepify after each insertion
  5. #include<iostream>
  6. #include<new>
  7. using namespace std;
  8. void hepify(int *heap,int i,int heapSize);
  9. void Display(int heap[],int heapSize);
  10. main(){
  11. //initialise array of required heap size
  12.     int heapSize;
  13.     cout<<"Enter max element in heap :- "<<endl;
  14.     cin>>heapSize;
  15.     int *heap;
  16.     heap =new int[heapSize+1];
  17.     heap[0]=0;
  18.     //now insert all element in heap
  19.     //after that we hepify it
  20.     cout<<"Enter element of heap :"<<endl;
  21.     //int a;
  22.     for(int i=1;i<=heapSize;i++){
  23.         cin>>heap[i];
  24.     }
  25.     cout<<"\nInsert data to form complete binary tree :"<<endl;
  26.     //some rightmost child may not present at at last level of heap
  27.     Display(heap,heapSize);
  28.     // now balance heap
  29.     for(int i=heapSize/2;i>=1;i--){
  30.         hepify(heap,i,heapSize);
  31.     }
  32.     //After Balancing Heap
  33.     cout<<"\nAfter Balancing Complete binary tree"<<endl;
  34.     cout<<"such that it become a heap. ie after heapify :)"<<endl;
  35.     Display(heap,heapSize);
  36. }
  37. void hepify(int *heap,int i,int heapSize){
  38.     int left=2*i; //index of left child of ith node
  39.     int right=left+1; //index of right child of ith node
  40.     int largest;
  41.     //find index of largest among (ith node and its left and right child)
  42.     if(left<=heapSize && heap[left]>heap[i])
  43.         largest=left;
  44.     else
  45.         largest=i;
  46.     if(right<=heapSize && heap[right]>heap[largest])
  47.         largest=right;
  48.     //now swap largest with ith node
  49.     if(largest !=i){
  50.         int temp =heap[i];
  51.         heap[i]=heap[largest];
  52.         heap[largest]=temp;
  53.         hepify(heap,largest,heapSize);
  54.     }
  55. }
  56. void Display(int heap[],int heapSize){
  57.     cout<<"Heap !!! >>>  ";
  58.     for(int i=1;i<=heapSize;i++){
  59.         cout<<heap[i]<<" ";
  60.     }
  61.     cout<<endl;
  62. }


Output

44 comments:

  1. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in Data Science with Python , kindly contact us http://www.maxmunus.com/contact
    MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.
    For Demo Contact us.
    Sangita Mohanty
    MaxMunus
    E-mail: sangita@maxmunus.com
    Skype id: training_maxmunus
    Ph:(0) 9738075708 / 080 - 41103383
    http://www.maxmunus.com/

    ReplyDelete
  2. Mesmerized article written on this blog with other relevant information. It is straight to the point that how we can improve our skills as well as how we can be represented to a new stream of professionalism.
    Dell Media Tape Cartridge for LTO6

    ReplyDelete
  3. Sometime few educational blogs become very helpful while getting relevant and new information related to your targeted area. As I found this blog and appreciate the information delivered to my database.
    create your own shirt

    ReplyDelete
  4. Share great information about your blog , Blog really helpful for us . We read your blog , share most useful information in blog . Thanks for share your blog here .
    รักษาไมเกรน

    ReplyDelete
  5. I welcome all the suggestion mentioned in this blog related to new learning skills. It is definitely going to help me to adopt new exited way of learning. I think, others will also feel helpful this blog for their needs.
    exness คือ

    ReplyDelete
  6. Sometime few educational blogs become very helpful while getting relevant and new information related to your targeted area. As I found this blog and appreciate the information delivered to my database.
    exness ข้อดี

    ReplyDelete
  7. Nice to read this publication on this blog. As far as I can see, this is a very basic question for everyone indeed. Its my personal opinion and I am completely agreed with the subject used here
    โปรโมชั่น เอไอเอส

    ReplyDelete
  8. creativity of writer is purely impressive. It has touched to the level of expertise with his writing. Everything is up to the mark. Written perfectly and I can use such information for my coming assignment.
    FBS โกงหรือไม่

    ReplyDelete
  9. This is really nice to read content of this blog. A is very extensive and vast knowledgeable platform has been given by this blog. I really appreciate this blog to has such kind of educational knowledge.
    สรรพคุณเห็ดหลินจือ

    ReplyDelete
  10. Mesmerized article written on this blog with other relevant information. It is straight to the point that how we can improve our skills as well as how we can be represented to a new stream of professionalism.
    โรงพิมพ์ออฟเซ็ท

    ReplyDelete
  11. Enthusiastic words written in this blog helped me to enhance my skills as well as helped me to know how I can help myself on my own. I am really glad to come at this platform.
    การ เล่น forex

    ReplyDelete
  12. I constantly like to read a top quality content having accurate info pertaining to the subject and the exact same thing I found in this article. Nice job.
    เช่า จอ

    ReplyDelete
  13. An author must have a vast knowledge of vocabulary. The dictionary of a writer must be full of new english vocabulary to make their work more attractive. Use of new words makes their work more valuable and graceful.
    E-Currency

    ReplyDelete
  14. Hey, It really is incredibly fantastic and informative website. Good to discover your site Very well article! I’m simply in love with it.
    เรซูเม่

    ReplyDelete
  15. I enjoyed reading this blog. in my opinion, everything was perfectly written there as well as few small tips are also can be taken as healthy suggestion. Descriptive informative content written in this blog is very useful.
    forex ไทย

    ReplyDelete
  16. our enthusiasm leads you beyond the limits. When you feel yourself enthusiastic that’s the time you can cross any limit. You seek to get perfection by using the ability of work. Read such motivational article and definitely it will help you to know new facts.
    Lenovo System x3500 M5

    ReplyDelete
  17. The site is really beneficial for everyone to know about this topic. I think if you read blog than you will get some more information from blog. This is really useful blog.
    pueraria mirifica

    ReplyDelete
  18. Now day, everything is going to find a new but well settled and successful stream for their career. When I came to this blog, I really impressed by all the knowledge points mentioned here. Thank you for this assistance.
    ขาย อะไร ดี

    ReplyDelete
  19. Professionally written blogs are rare to find, however I appreciate all the points mentioned here. I also want to include some other writing skills which everyone must aware of.
    epoxy resin คือ

    ReplyDelete
  20. Professionally written blogs are rare to find, however I appreciate all the points mentioned here. I also want to include some other writing skills which everyone must aware of.
    ใบ อนุญาต เครื่องมือ แพทย์

    ReplyDelete
  21. Really inspirational to hear someone pursuing their dreams and becoming successful instead of following the traditional path. I have read your article about This topic. I think it's good and impressed to know your service. Thanks for share this Information.
    ราคาแอร์

    ReplyDelete
  22. Enthusiastic beginning is very common in every sector when anyone enters into a new world. But it is very hard to keep such enthusiasm for a long time after huddles come out from invited sources. Read this blog and know more about this topic.
    forex demo

    ReplyDelete
  23. I am delighted to come to such a wonderful blog. I am really very impressed to read from top to bottom. I read every single line and understand the essence of every single word. I appreciate all efforts.
    Web Design

    ReplyDelete
  24. Professionally written blogs are rare to find, however I appreciate all the points mentioned here. I also want to include some other writing skills which everyone must aware of.
    โปรโมชั่น iphone

    ReplyDelete
  25. Detailed and descriptive articles written in this blog is really very helpful for me as well as for other who seeking such kind of knowledge. It is definitely going to become useful in coming future.
    ออกแบบกระเป๋าผ้า

    ReplyDelete
  26. This blog is really helpful regarding all educational knowledge I earned. It covered a great area of subject which can assist a lot of needy people. Everything mentioned here is clear and very useful.
    Affiliate คืออะไร

    ReplyDelete
  27. Professionally written blogs are rare to find, however I appreciate all the points mentioned here. I also want to include some other writing skills which everyone must aware of.
    หุ้น forex

    ReplyDelete
  28. Hello, I also would like to comment over all the points mentioned in this blog. I agree with essence of few point but somewhere I found myself on other place. I hope, there might little opinion of others as well.
    เรียน a level ที่ไหนดี

    ReplyDelete
  29. That’s what I was looking for. I am talking about all topics bundled in this blog. They all are really very useful for me as well as for my team. We are definitely going to use its highlighted information.
    ฟ อ เร็ ก

    ReplyDelete
  30. Sometimes is becomes very hard to take appreciation for your hard work. But sometime only few technical point makes your work worthwhile. Suggestion under this blog is quite good.
    canvas tote

    ReplyDelete
  31. Your blog is very informative. Eating mindfully has been very hard for people these days. It's all because of their busy schedules, work or lack of focus on themselves. As a student I must admit that I have not been eating mindfully but because of this I will start now. It could help me enjoy my food and time alone. Eating mindfully may help me be aware of healthy food and appreciating food.
    โปร Advice

    ReplyDelete
  32. This blog is truly useful to convey overhauled instructive undertakings over web which is truly examination. I discovered one fruitful case of this truth through this blog. I will utilize such data now.
    โคม ไฟ โรงงาน

    ReplyDelete
  33. This blog is really helpful regarding all educational knowledge I earned. It covered a great area of subject which can assist a lot of needy people. Everything mentioned here is clear and very useful.
    เร ซิ่น

    ReplyDelete
  34. This blog is really helpful regarding all educational knowledge I earned. It covered a great area of subject which can assist a lot of needy people. Everything mentioned here is clear and very useful.
    เร ซิ่น

    ReplyDelete
  35. Professionally written blogs are rare to find, however I appreciate all the points mentioned here. I also want to include some other writing skills which everyone must aware of.
    Put Option คือ

    ReplyDelete
  36. It become an attractive part of a blog when author uses indirect speech while writing a blog. It shows your creative mind as well as make your written essay different from others.
    Forex Bitcoin คือ

    ReplyDelete
  37. Wow, a great code. I dont know the function lol
    Mobil SUV Terbaru

    ReplyDelete
  38. An outstanding share! I've just forwarded this onto a co-worker who has been doing a little research on this. And he actually bought me dinner because I discovered it for him... lol. So let me reword this.... Thank YOU for the meal!! But yeah, thanx for spending time to discuss this issue here on your web page.
    cây treo quần áo

    ReplyDelete
  39. I blog quite often and I genuinely thank you for your information. Your article has truly peaked my interest. I will book mark your blog and keep checking for new information about once per week. I opted in for your Feed too.
    bàn ăn gỗ giá rẻ

    ReplyDelete
  40. This is a topic which is near to my heart... Best wishes! Exactly where are your contact details though?
    giường ngủ đẹp

    ReplyDelete
  41. Amazing blog! Is your theme custom made or did you download it from somewhere? A design like yours with a few simple adjustements would really make my blog jump out. Please let me know where you got your design. Cheers 토토사이트


    ------------------------------------------------------------------------------

    I simply wished to say thanks once more. I am not sure the things I would’ve used in the absence of the entire thoughts discussed by you on this industry. It had been a real intimidating issue in my view, however , looking at the very skilled style you solved the issue took me to leap over contentment. I am just happier for this support and then hope you recognize what an amazing job you are doing instructing most people thru your web page. I know that you haven’t met all of us. 메이저리그중계

    ReplyDelete
  42. I am continually browsing online for ideas that can aid me. Thanks! https://royalcbd.com/product/cbd-salve/

    ReplyDelete
  43. This is really too useful and have more ideas and keep sharing many techniques...you can explore the many exciting Job Opportunities on India Postal Recruitment 2020. Latest and also upcoming Notifications on India Post recruitment are updated in this page immediately... good luck

    Ai & Artificial Intelligence Course in Chennai
    PHP Training in Chennai
    Ethical Hacking Course in Chennai Blue Prism Training in Chennai
    UiPath Training in Chennai

    ReplyDelete

THANKS FOR UR GREAT COMMENT

Blogger Widgets