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

48 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. I have read your blog and I gathered some needful information from your blog. Keep update your blog. Awaiting for your next update.
    Php course in chennai

    ReplyDelete
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. Sometime it becomes very hard to find a well written and well established bog which give you correct and useful information. However, I found this blog and got some relevant information which are really helpful for me.
    air bubble

    ReplyDelete
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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.
    สอน เล่น forex

    ReplyDelete
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  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.
    ใบ อนุญาต เครื่องมือ แพทย์

    ReplyDelete
  25. 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
  26. 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
  27. 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
  28. Graceful written content on this blog is really useful for everyone same as I got to know. Difficult to locate relevant and useful informative blog as I found this one to get more knowledge but this is really a nice one.
    รับวาดรูปการ์ตูน

    ReplyDelete
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. Wow! This is the perfect blog I am looking this type of blog its awesome blog here , share great information about this topic. This informative blog helps many readers with their decision-making regarding the situation. Great articles and will look forward for more!
    โคม ไฟ ถนน

    ReplyDelete
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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 .
    a level

    ReplyDelete
  46. 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
  47. 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
  48. Wow, a great code. I dont know the function lol
    Mobil SUV Terbaru

    ReplyDelete

THANKS FOR UR GREAT COMMENT

Blogger Widgets