힙이란 무엇입니까?
힙은 완전한 이진 트리이고, 이진 트리는 노드가 최대 2개의 자식을 가질 수 있는 트리입니다. 힙에 대해 더 알아보기 전에 완전 이진 트리란 무엇입니까?
완전 이진 트리는 마지막 레벨, 즉 리프 노드를 제외한 모든 레벨이 완전히 채워지고 모든 노드가 왼쪽 정렬되는 이진 트리입니다.
예를 통해 이해해 봅시다.
위 그림에서 리프 노드를 제외하고 모든 내부 노드가 완전히 채워지는 것을 볼 수 있습니다. 그러므로 위의 트리는 완전한 이진 트리라고 말할 수 있습니다.
위 그림에서는 리프 노드를 제외한 모든 내부 노드가 완전히 채워졌으나 리프 노드는 오른쪽 부분에 추가된 것을 보여줍니다. 그러므로 위의 트리는 완전한 이진 트리가 아닙니다.
참고: 힙 트리는 루트 노드가 하위 노드와 비교되어 그에 따라 정렬되는 특별한 균형 이진 트리 데이터 구조입니다.
트리의 노드를 어떻게 배열할 수 있나요?
힙에는 두 가지 유형이 있습니다.
UDP 프로토콜
- 최소 힙
- 최대 힙
최소 힙: 상위 노드의 값은 하위 노드 중 하나보다 작거나 같아야 합니다.
또는
즉, 최소힙은 모든 노드 i에 대해 루트 노드를 제외한 노드 i의 값이 상위 노드보다 크거나 같다고 정의할 수 있습니다. 수학적으로는 다음과 같이 정의할 수 있습니다.
A[부모(i)]<= a[i]< strong>
에디스 맥 허쉬
예제를 통해 최소힙을 이해해보자.
위 그림에서 11은 루트 노드이고, 루트 노드의 값은 다른 모든 노드(왼쪽 자식 또는 오른쪽 자식)의 값보다 작습니다.
최대 힙: 상위 노드의 값은 하위 노드보다 크거나 같습니다.
또는
즉, 최대 힙은 모든 노드 i에 대해 정의될 수 있습니다. 노드 i의 값은 루트 노드를 제외한 상위 값보다 작거나 같습니다. 수학적으로는 다음과 같이 정의할 수 있습니다.
자바스크립트 드롭다운
A[부모(i)] >= A[i]
위 트리는 최대 힙의 속성을 만족하는 최대 힙 트리이다. 이제 최대 힙의 배열 표현을 살펴보겠습니다.
최대 힙의 시간 복잡도
최대 힙에 필요한 총 비교 횟수는 트리 높이에 따라 다릅니다. 완전한 이진 트리의 높이는 항상 로그됩니다. 따라서 시간복잡도도 O(logn)이 됩니다.
최대 힙에서의 삽입 작업 알고리즘.
// 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])>