Binary Heap Data Structure in Computer Engineering
Explore the concept of binary heap in computer engineering with its properties, types (max heap and min heap), and the process of building a heap. Learn how to construct a max binary heap with a practical example. Discover the significance of heapness and heap structure in optimizing data storage and retrieval.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
BINARY HEAP 9 8 4 7 6 2 3 PROF AJITKUMAR SHITOLE ASSISTANT PROFESSOR DEPARTMENT OF COMPUTER ENGINEERING 1 HOPE FOUNDATION S INTERNATIONAL INSTITUTE OF INFORMATION TECHNOLOGY, I IT WWW.ISQUAREIT.EDU.IN 1
BINARY HEAP SPECIAL TYPE OF A BINARY TREE. TWO PROPERTIES MUST BE SATISFIED. COMPLETENESS / HEAP STRUCTURE: BINARY TREE IS EITHER COMPLETE OR ALMOST COMPLETE BINARY TREE IN WHICH ALL LEVELS ARE COMPLETELY FILLED FROM TOP TO BOTTOM AND LEFT TO RIGHT EXCEPT BOTTOMMOST LEVEL WHICH MAY OR MAY NOT BE FILLED COMPLETELY. HEAPNESS / HEAP ORDER: THE VALUE OF PARENT NODE IS GREATER THAN EITHER CHILD IN CASE OF MAX HEAP AND IS LESS THAN EITHER CHILD IN CASE OF MIN HEAP. 2 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
BINARY HEAP 1. MAX HEAP: A HEAP IS A BINARY TREE IN WHICH EVERY PARENT NODE VALUE IS GREATER THAN ITS CHILDREN. 2. MIN HEAP: A HEAP IS A BINARY TREE IN WHICH EVERY PARENT NODE VALUE IS SMALLER THAN ITS CHILDREN. 3 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
BINARY HEAP TO BUILD A HEAP, DATA IS PLACED IN THE TREE AS IT ARRIVES. ALGORITHM: 1. 2. 3. INSERT NEW NODE AT THE NEXT LEAF POSITION USE THIS NEW NODE AS THE CURRENT POSITION WHILE NEW DATA IS GREATER THAN THAT IN THE PARENT OF THE CURRENT NODE: MOVE THE PARENT DOWN TO THE CURRENT NODE MAKE THE PARENT (NOW VACANT) THE CURRENT NODE PLACE DATA IN CURRENT NODE 4 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
BINARY HEAP AS NEW NODE IS ALWAYS INSERTED AT THE LAST LEVEL, HEAP NEVER BECOMES UNBALANCED. A HEAP IS A PARTIALLY SORTED DATA STRUCTURE. A GIVEN SET OF DATA CAN BE FORMED INTO MANY DIFFERENT HEAPS (DEPENDS ON THE ORDER IN WHICH THE DATA ARRIVES.) 5 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
BUILDING MAX BINARY HEAP EXAMPLE: DATA ARRIVES TO BE HEAPED IN THE ORDER: 55, 88, 28, 68, 20, 32, 30, 19, 33 6 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
MAX BINARY HEAP 55, 88, 28, 68, 20, 32, 30, 19, 33 55 88 88 55 55 55 28 88 88 88 88 55 28 68 28 68 28 68 55 7 55 20 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
MAX BINARY HEAP 55, 88, 28, 68, 20, 32, 30, 19, 33 88 88 68 28 68 28 20 55 20 32 55 8 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
MAX BINARY HEAP 55, 88, 28, 68, 20, 32, 30, 19, 33 88 88 68 32 68 32 20 28 30 55 20 28 30 55 19 33 9 Hope Foundation s International Institute of Information Technology, I IT P-14,Rajiv Gandhi Infotech Park MIDC Phase 1, Hinjawadi, Pune 411057 Tel - +91 20 22933441/2/3 | www.isquareit.edu.in | info@isquareit.edu.in
THANK YOU FOR FURTHER INFORMATION PLEASE CONTACT PROF. AJITKUMAR SHITOLE DEPARTMENT OF COMPUTER ENGINEERING HOPE FOUNDATION S INTERNATIONAL INSTITUTE OF INFORMATION TECHNOLOGY, I IT HINJAWADI, PUNE 411 057 PHONE - +91 20 22933441 WWW.ISQUAREIT.EDU.IN | AJITKUMARS@ISQUAREIT.EDU.IN | INFO@ISQUAREIT.EDU.IN 10
