Kas yra Krūva?
Krūva yra pilnas dvejetainis medis, o dvejetainis medis yra medis, kuriame mazgas gali turėti daugiausiai du vaikus. Prieš sužinodami daugiau apie krūvą Kas yra pilnas dvejetainis medis?
Pilnas dvejetainis medis yra a dvejetainis medis, kuriame visi lygiai, išskyrus paskutinį lygį, t. y. lapo mazgas, turi būti visiškai užpildyti, o visi mazgai turi būti išlyginti kairėje pusėje.
a-b genėjimas
Supraskime per pavyzdį.
Aukščiau pateiktame paveikslėlyje galime pastebėti, kad visi vidiniai mazgai yra visiškai užpildyti, išskyrus lapo mazgą; todėl galime sakyti, kad aukščiau pateiktas medis yra pilnas dvejetainis medis.
Aukščiau pateiktame paveikslėlyje parodyta, kad visi vidiniai mazgai yra visiškai užpildyti, išskyrus lapo mazgą, bet lapo mazgai pridedami prie dešinės dalies; todėl aukščiau pateiktas medis nėra pilnas dvejetainis medis.
Pastaba: krūvos medis yra speciali subalansuota dvejetainio medžio duomenų struktūra, kurioje šakninis mazgas lyginamas su antriniais mazgais ir atitinkamai išdėstomas.
Kaip galime išdėstyti mazgus medyje?
Yra dviejų tipų krūvos:
- Min. krūva
- Maksimali krūva
Min. krūva: Pirminio mazgo vertė turi būti mažesnė arba lygi bet kuriam iš antrinių.
Arba
nuorodos rodyklė c
Kitaip tariant, min krūva gali būti apibrėžta taip, kad kiekvieno mazgo i mazgo i reikšmė yra didesnė arba lygi jo pirminei vertei, išskyrus šakninį mazgą. Matematiškai jį galima apibrėžti taip:
A[Tėvas (i)]<= a[i]< strong>
Supraskime min krūvą per pavyzdį.
Aukščiau pateiktame paveikslėlyje 11 yra šakninis mazgas, o šakninio mazgo reikšmė yra mažesnė nei visų kitų mazgų (kairiojo antrinio arba dešiniojo antrinio).
Didžiausia krūva: Pirminio mazgo vertė yra didesnė arba lygi antriniams.
Arba
Kitaip tariant, maksimali krūva gali būti apibrėžta kaip kiekvienam mazgui i; mazgo i reikšmė yra mažesnė arba lygi jo pirminei vertei, išskyrus šakninį mazgą. Matematiškai jį galima apibrėžti taip:
A[Parent(i)] >= A[i]
java int į dvigubą
Aukščiau pateiktas medis yra maksimalaus krūvos medis, nes jis atitinka didžiausios krūvos savybę. Dabar pažiūrėkime didžiausios krūvos masyvo atvaizdavimą.
Laiko sudėtingumas Max Heap
Bendras palyginimų skaičius, kurio reikia maksimalioje krūvoje, priklauso nuo medžio aukščio. Viso dvejetainio medžio aukštis visada yra logn; todėl laiko sudėtingumas taip pat būtų O(logn).
Įterpimo operacijos maksimalioje krūvoje algoritmas.
// algorithm to insert an element in the max heap. insertHeap(A, n, value) { n=n+1; // n is incremented to insert the new element A[n]=value; // assign new value at the nth position i = n; // assign the value of n to i // loop will be executed until i becomes 1. while(i>1) { parent= floor value of i/2; // Calculating the floor value of i/2 // Condition to check whether the value of parent is less than the given node or not if(A[parent] <a[i]) { swap(a[parent], a[i]); i="parent;" } else return; < pre> <p> <strong>Let's understand the max heap through an example</strong> .</p> <p>In the above figure, 55 is the parent node and it is greater than both of its child, and 11 is the parent of 9 and 8, so 11 is also greater than from both of its child. Therefore, we can say that the above tree is a max heap tree.</p> <p> <strong>Insertion in the Heap tree</strong> </p> <p> <strong>44, 33, 77, 11, 55, 88, 66</strong> </p> <p>Suppose we want to create the max heap tree. To create the max heap tree, we need to consider the following two cases:</p> <ul> <li>First, we have to insert the element in such a way that the property of the complete binary tree must be maintained.</li> <li>Secondly, the value of the parent node should be greater than the either of its child.</li> </ul> <p> <strong>Step 1:</strong> First we add the 44 element in the tree as shown below:</p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-5.webp" alt="Heap Data Structure"> <p> <strong>Step 2:</strong> The next element is 33. As we know that insertion in the binary tree always starts from the left side so 44 will be added at the left of 33 as shown below:</p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-6.webp" alt="Heap Data Structure"> <p> <strong>Step 3:</strong> The next element is 77 and it will be added to the right of the 44 as shown below:</p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-7.webp" alt="Heap Data Structure"> <p>As we can observe in the above tree that it does not satisfy the max heap property, i.e., parent node 44 is less than the child 77. So, we will swap these two values as shown below:</p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-8.webp" alt="Heap Data Structure"> <p> <strong>Step 4:</strong> The next element is 11. The node 11 is added to the left of 33 as shown below:</p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-9.webp" alt="Heap Data Structure"> <p> <strong>Step 5:</strong> The next element is 55. To make it a complete binary tree, we will add the node 55 to the right of 33 as shown below:</p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-10.webp" alt="Heap Data Structure"> <p>As we can observe in the above figure that it does not satisfy the property of the max heap because 33<55, so we will swap these two values as shown below:< p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-11.webp" alt="Heap Data Structure"> <p> <strong>Step 6:</strong> The next element is 88. The left subtree is completed so we will add 88 to the left of 44 as shown below:</p> <img src="//techcodeview.com/img/ds-tutorial/89/heap-data-structure-12.webp" alt="Heap Data Structure"> <p>As we can observe in the above figure that it does not satisfy the property of the max heap because 44<88, so we will swap these two values as shown below:< p> <p>Again, it is violating the max heap property because 88>77 so we will swap these two values as shown below:</p> <p> <strong>Step 7:</strong> The next element is 66. To make a complete binary tree, we will add the 66 element to the right side of 77 as shown below:</p> <p>In the above figure, we can observe that the tree satisfies the property of max heap; therefore, it is a heap tree.</p> <p> <strong>Deletion in Heap Tree</strong> </p> <p>In Deletion in the heap tree, the root node is always deleted and it is replaced with the last element.</p> <p> <strong>Let's understand the deletion through an example.</strong> </p> <p> <strong>Step 1</strong> : In the above tree, the first 30 node is deleted from the tree and it is replaced with the 15 element as shown below:</p> <p>Now we will heapify the tree. We will check whether the 15 is greater than either of its child or not. 15 is less than 20 so we will swap these two values as shown below:</p> <p>Again, we will compare 15 with its child. Since 15 is greater than 10 so no swapping will occur.</p> <p> <strong>Algorithm to heapify the tree</strong> </p> <pre> MaxHeapify(A, n, i) { int largest =i; int l= 2i; int r= 2i+1; while(lA[largest]) { largest=l; } while(rA[largest]) { largest=r; } if(largest!=i) { swap(A[largest], A[i]); heapify(A, n, largest); }} </pre> <hr></88,></p></55,></p></a[i])>