Max-Heap 소개 – 데이터 구조 및 알고리즘 튜토리얼
ㅏ 최대 힙 의 유형으로 정의됩니다. 힙 데이터 구조는 데이터 정렬, 검색 및 구성을 비롯한 다양한 목적으로 컴퓨터 과학에서 일반적으로 사용되는 이진 트리 유형입니다.
Max-Heap 데이터 구조 소개
Max-Heap의 목적 및 사용 사례:
- 우선순위 대기열: 힙 데이터 구조의 주요 용도 중 하나는 우선순위 큐를 구현하는 것입니다.
- 힙 정렬: 힙 데이터 구조는 정렬 알고리즘에도 사용됩니다.
- 메모리 관리: 힙 데이터 구조는 메모리 관리에도 사용됩니다. 프로그램이 메모리를 동적으로 할당해야 하는 경우 힙 데이터 구조를 사용하여 사용 가능한 메모리를 추적합니다.
- Dijkstra의 최단 경로 알고리즘 힙 데이터 구조를 사용하여 소스 정점에서 가장 짧은 경로를 가진 정점을 추적합니다.
다양한 언어의 Max-Heap 데이터 구조:
1. C++의 최대 힙
최대 힙은 다음을 사용하여 구현할 수 있습니다. 우선순위_큐 컨테이너에서 표준 템플릿 라이브러리(STL) . 그만큼 우선순위_큐 컨테이너는 각 요소에 연관된 우선순위가 있는 대기열과 같은 데이터 구조에 요소를 저장하는 방법을 제공하는 컨테이너 어댑터 유형입니다.
Synt ax: priority_queuemaxH;2. Java의 최대 힙
Java에서는 다음을 사용하여 최대 힙을 구현할 수 있습니다. 우선순위 대기열 수업 java.util 패키지 . PriorityQueue 클래스는 각 요소에 연관된 우선순위가 있는 대기열과 같은 데이터 구조에 요소를 저장하는 방법을 제공하는 우선순위 대기열입니다.
Syntax : PriorityQueue maxHeap= new PriorityQueue(Comparator.reverseOrder());삼. Python의 최대 힙
Python에서는 다음을 사용하여 최대 힙을 구현할 수 있습니다. 힙 힙 구현을 위한 기능을 제공하는 모듈입니다. 특히 heapq 모듈은 힙 데이터 구조를 생성하고 조작하는 방법을 제공합니다.
Synt ax: heap = [] heapify(heap)4. C#의 최대 힙
C#에서는 다음의 PriorityQueue 클래스를 사용하여 최대 힙을 구현할 수 있습니다. System.Collections.Generic 네임스페이스 . PriorityQueue 클래스는 각 요소에 연관된 우선순위가 있는 대기열과 같은 데이터 구조에 요소를 저장하는 방법을 제공하는 우선순위 대기열입니다.
Syntax: var maxHeap = new PriorityQueue((a, b) =>b-a);5. JavaScript의 최대 힙
최대 힙은 모든 노드가 해당 하위 노드보다 크거나 같은 값을 갖는 이진 트리입니다. JavaScript에서는 배열을 사용하여 최대 힙을 구현할 수 있습니다. 여기서 첫 번째 요소는 루트 노드를 나타내고 노드의 하위 항목은 인덱스를 나타냅니다. 나 인덱스에 위치 2i+1 그리고 2i+2.
Syntax: const miaxHeap = new MaxHeap();최대 힙과 최소 힙의 차이점
최소 힙 최대 힙 1. 최소 힙에서 루트 노드에 있는 키는 모든 하위 노드에 있는 키보다 작거나 같아야 합니다. Max-Heap에서 루트 노드에 있는 키는 모든 하위 노드에 있는 키보다 크거나 같아야 합니다. 2. 최소 힙에서는 루트에 존재하는 최소 키 요소입니다. Max-Heap에서는 루트에 존재하는 최대 키 요소입니다. 삼. 최소 힙은 오름차순 우선순위를 사용합니다. Max-Heap은 내림차순 우선순위를 사용합니다. 4. Min-Heap을 구성할 때 가장 작은 요소가 우선순위를 갖습니다. Max-Heap 구성에서는 가장 큰 요소가 우선순위를 갖습니다. 5. 최소 힙에서는 가장 작은 요소가 힙에서 가장 먼저 팝됩니다. Max-Heap에서는 가장 큰 요소가 힙에서 가장 먼저 팝됩니다. Max-Heap 데이터 구조의 내부 구현:
ㅏ 최소 힙은 일반적으로 배열로 표시됩니다. .
- 루트 요소는 다음 위치에 있습니다. 도착[0] .
- 임의의 i번째 노드에 대해 도착[i].
- 왼쪽 자식은 인덱스에 저장됨 2i+1
- 오른쪽 자식은 인덱스에 저장됩니다. 2i+2
- 상위 항목은 인덱스 층에 저장됩니다. ((i-1)/2)
Max-Heap의 내부 구현에는 3가지 주요 단계가 필요합니다.
- 삽입 : 새 요소를 힙에 삽입하려면 배열 끝에 추가한 다음 힙 속성을 만족할 때까지 버블링합니다.
- 삭제 : 최대 요소(힙의 루트)를 삭제하려면 배열의 마지막 요소를 루트로 교체하고 새 루트는 힙 속성을 만족할 때까지 버블링됩니다.
- 힙파이 : heapify 작업을 사용하면 정렬되지 않은 배열에서 최대 힙을 생성할 수 있습니다.
Max-heap 데이터 구조에 대한 작업 및 구현:
다음은 힙 데이터 구조 데이터 구조에서 수행할 수 있는 몇 가지 일반적인 작업입니다.
1. Max-Heap 데이터 구조에 삽입 :
삭제에 대해 위에서 설명한 것과 유사한 접근 방식에 따라 요소를 힙에 삽입할 수 있습니다. 아이디어는 다음과 같습니다.
- 먼저 새 요소를 저장할 수 있도록 힙 크기를 1씩 늘립니다.
- 힙 끝에 새 요소를 삽입합니다.
- 새로 삽입된 이 요소는 상위 요소에 대한 힙 속성을 왜곡할 수 있습니다. 따라서 Heap의 속성을 유지하려면 상향식 접근 방식에 따라 새로 삽입된 요소를 힙화하세요.
삽화:
힙이 다음과 같이 Max-Heap이라고 가정합니다.
최대 힙에 삽입
Max-Heap에 삽입 작업 구현:
C++
// C++ program to insert new element to Heap>#include>using>namespace>std;>#define MAX 1000 // Max size of Heap>// Function to heapify ith node in a Heap>// of size n following a Bottom-up approach>void>heapify(>int>arr[],>int>n,>int>i)>{>>// Find parent>>int>parent = (i - 1) / 2;>>if>(arr[parent]>0) {>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>도착[부모]) {>>swap(arr[i], arr[parent]);>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>}>// Function to insert a new node to the Heap>void>insertNode(>int>arr[],>int>& n,>int>Key)>{>>// Increase the size of Heap by 1>>n = n + 1;>>// Insert the element at end of Heap>>arr[n - 1] = Key;>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n - 1);>}>// A utility function to print array of size n>void>printArray(>int>arr[],>int>n)>{>>for>(>int>i = 0; i cout < < arr[i] < < ' '; cout < < ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[MAX] = { 10, 5, 3, 2, 4 }; int n = 5; int key = 15; insertNode(arr, n, key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 return 0; }>
자바
// Java program for implementing insertion in Heaps>public>class>insertionHeap {>>// Function to heapify ith node in a Heap>>// of size n following a Bottom-up approach>>static>void>heapify(>int>[] arr,>int>n,>int>i)>>{>>// Find parent>>int>parent = (i ->1>) />2>;>>>if>(arr[parent]>>0>) {>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>도착[부모]) {>>>// swap arr[i] and arr[parent]>>int>temp = arr[i];>>arr[i] = arr[parent];>>arr[parent] = temp;>>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>>}>>// Function to insert a new node to the heap.>>static>int>insertNode(>int>[] arr,>int>n,>int>Key)>>{>>// Increase the size of Heap by 1>>n = n +>1>;>>>// Insert the element at end of Heap>>arr[n ->1>] = Key;>>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n ->1>);>>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size n */>>static>void>printArray(>int>[] arr,>int>n)>>{>>for>(>int>i =>0>; i System.out.println(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // The code is contributed by Gautam goel>
씨#
// C# program for implementing insertion in Heaps>using>System;>public>class>insertionHeap {>>// Function to heapify ith node in a Heap of size n following a Bottom-up approach>>static>void>heapify(>int>[] arr,>int>n,>int>i) {>>// Find parent>>int>parent = (i - 1) / 2;>>if>(arr[parent]>0) {>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>도착[부모]) {>>// swap arr[i] and arr[parent]>>int>temp = arr[i];>>arr[i] = arr[parent];>>arr[parent] = temp;>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>>}>>// Function to insert a new node to the heap.>>static>int>insertNode(>int>[] arr,>int>n,>int>Key) {>>// Increase the size of Heap by 1>>n = n + 1;>>// Insert the element at end of Heap>>arr[n - 1] = Key;>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n - 1);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size n */>>static>void>printArray(>int>[] arr,>int>n) {>>for>(>int>i = 0; i Console.WriteLine(arr[i] + ' '); Console.WriteLine(''); } public static void Main(string[] args) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 // maximum size of the array int MAX = 1000; int[] arr = new int[MAX]; // initializing some values arr[0] = 10; arr[1] = 5; arr[2] = 3; arr[3] = 2; arr[4] = 4; // Current size of the array int n = 5; // the element to be inserted int Key = 15; // The function inserts the new element to the heap and // returns the new size of the array n = insertNode(arr, n, Key); printArray(arr, n); // Final Heap will be: // 15 // / // 5 10 // / / // 2 4 3 } } // This code is contributed by ajaymakvana.>
자바스크립트
// Javascript program for implement insertion in Heaps>// To heapify a subtree rooted with node i which is>// an index in arr[].Nn is size of heap>let MAX = 1000;>// Function to heapify ith node in a Heap of size n following a Bottom-up approach>function>heapify(arr, n, i)>{>>// Find parent>>let parent = Math.floor((i-1)/2);>>if>(arr[parent]>= 0) {>>// For Max-Heap>>// If current node is greater than its parent>>// Swap both of them and call heapify again>>// for the parent>>if>(arr[i]>도착[부모]) {>>let temp = arr[i];>>arr[i] = arr[parent];>>arr[parent] = temp;>>// Recursively heapify the parent node>>heapify(arr, n, parent);>>}>>}>}>// Function to insert a new node to the Heap>function>insertNode(arr, n, Key)>{>>// Increase the size of Heap by 1>>n = n + 1;>>// Insert the element at end of Heap>>arr[n - 1] = Key;>>// Heapify the new node following a>>// Bottom-up approach>>heapify(arr, n, n - 1);>>>return>n;>}>/* A utility function to print array of size N */>function>printArray(arr, n)>{>>for>(let i = 0; i console.log(arr[i] + ' '); console.log(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; let key = 15; n = insertNode(arr, n, key); printArray(arr, n); // This code is contributed by ajaymakvana>
파이썬3
# program to insert new element to Heap># Function to heapify ith node in a Heap># of size n following a Bottom-up approach>def>heapify(arr, n, i):>>parent>=>int>(((i>->1>)>/>2>))>># For Max-Heap>># If current node is greater than its parent>># Swap both of them and call heapify again>># for the parent>>if>arr[parent]>>0>:>>if>arr[i]>도착[부모]:>>arr[i], arr[parent]>=>arr[parent], arr[i]>># Recursively heapify the parent node>>heapify(arr, n, parent)># Function to insert a new node to the Heap>def>insertNode(arr, key):>>global>n>># Increase the size of Heap by 1>>n>+>=>1>># Insert the element at end of Heap>>arr.append(key)>># Heapify the new node following a>># Bottom-up approach>>heapify(arr, n, n>->1>)># A utility function to print array of size n>def>printArr(arr, n):>>for>i>in>range>(n):>>print>(arr[i], end>=>' '>)># Driver Code># Array representation of Max-Heap>'''>>10>>/>>5 3>>/>>2 4>'''>arr>=>[>10>,>5>,>3>,>2>,>4>,>1>,>7>]>n>=>7>key>=>15>insertNode(arr, key)>printArr(arr, n)># Final Heap will be:>'''>>15>>/>5 10>/ />2 4 3>Code is written by Rajat Kumar....>'''>
산출
15 5 10 2 4 3시간 복잡도: O(log(n)) ( 여기서 n은 힙에 요소가 없습니다. )
보조 공간: 에)2. Max-Heap 데이터 구조에서 삭제 :
힙의 중간 위치에서 요소를 삭제하는 것은 비용이 많이 들 수 있으므로 삭제할 요소를 마지막 요소로 교체하고 힙의 마지막 요소를 삭제하기만 하면 됩니다.
- 삭제할 루트 또는 요소를 마지막 요소로 바꿉니다.
- 힙에서 마지막 요소를 삭제합니다.
- 이제 마지막 요소가 루트 노드 위치에 배치됩니다. 따라서 힙 속성을 따르지 않을 수도 있습니다. 따라서 루트 위치에 있는 마지막 노드를 힙화한다.
삽화 :
힙이 다음과 같이 Max-Heap이라고 가정합니다.
최대 힙 데이터 구조
삭제할 요소는 루트, 즉 10입니다.
프로세스 :
마지막 요소는 4입니다.
1 단계: 마지막 요소를 루트로 바꾸고 삭제합니다.
최대 힙
2 단계 : 뿌리를 쌓으세요.
최종 힙:
최대 힙
Max-Heap에서 삭제 작업 구현:
C++
// C++ program for implement deletion in Heaps>#include>using>namespace>std;>// To heapify a subtree rooted with node i which is>// an index of arr[] and n is the size of heap>void>heapify(>int>arr[],>int>n,>int>i)>{>>int>largest = i;>// Initialize largest as root>>int>l = 2 * i + 1;>// left = 2*i + 1>>int>r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i) {>>swap(arr[i], arr[largest]);>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>}>// Function to delete the root from Heap>void>deleteRoot(>int>arr[],>int>& n)>{>>// Get the last element>>int>lastElement = arr[n - 1];>>// Replace root with last element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>}>/* A utility function to print array of size n */>void>printArray(>int>arr[],>int>n)>{>>for>(>int>i = 0; i cout < < arr[i] < < ' '; cout < < ' '; } // Driver Code int main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); deleteRoot(arr, n); printArray(arr, n); return 0; }>
자바
// Java program for implement deletion in Heaps>public>class>deletionHeap {>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>arr[],>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l =>2>* i +>1>;>// left = 2*i + 1>>int>r =>2>* i +>2>;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i) {>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>arr[],>int>n)>>{>>// Get the last element>>int>lastElement = arr[n ->1>];>>// Replace root with first element>>arr[>0>] = lastElement;>>// Decrease size of heap by 1>>n = n ->1>;>>// heapify the root node>>heapify(arr, n,>0>);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>arr[],>int>n)>>{>>for>(>int>i =>0>; i System.out.print(arr[i] + ' '); System.out.println(); } // Driver Code public static void main(String args[]) { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int arr[] = { 10, 5, 3, 2, 4 }; int n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); } }>
씨#
// C# program for implement deletion in Heaps>using>System;>public>class>deletionHeap>{>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>static>void>heapify(>int>[]arr,>int>n,>int>i)>>{>>int>largest = i;>// Initialize largest as root>>int>l = 2 * i + 1;>// left = 2*i + 1>>int>r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>int>swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>static>int>deleteRoot(>int>[]arr,>int>n)>>{>>// Get the last element>>int>lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>static>void>printArray(>int>[]arr,>int>n)>>{>>for>(>int>i = 0; i Console.Write(arr[i] + ' '); Console.WriteLine(); } // Driver Code public static void Main() { // Array representation of Max-Heap // 10 // / // 5 3 // / // 2 4 int []arr = { 10, 5, 3, 2, 4 }; int n = arr.Length; n = deleteRoot(arr, n); printArray(arr, n); } } // This code is contributed by Ryuga>
자바스크립트
>>// Javascript program for implement deletion in Heaps>>>// To heapify a subtree rooted with node i which is>>// an index in arr[].Nn is size of heap>>function>heapify(arr, n, i)>>{>>let largest = i;>// Initialize largest as root>>let l = 2 * i + 1;>// left = 2*i + 1>>let r = 2 * i + 2;>// right = 2*i + 2>>// If left child is larger than root>>if>(l arr[largest])>>largest = l;>>// If right child is larger than largest so far>>if>(r arr[largest])>>largest = r;>>// If largest is not root>>if>(largest != i)>>{>>let swap = arr[i];>>arr[i] = arr[largest];>>arr[largest] = swap;>>// Recursively heapify the affected sub-tree>>heapify(arr, n, largest);>>}>>}>>// Function to delete the root from Heap>>function>deleteRoot(arr, n)>>{>>// Get the last element>>let lastElement = arr[n - 1];>>// Replace root with first element>>arr[0] = lastElement;>>// Decrease size of heap by 1>>n = n - 1;>>// heapify the root node>>heapify(arr, n, 0);>>// return new size of Heap>>return>n;>>}>>/* A utility function to print array of size N */>>function>printArray(arr, n)>>{>>for>(let i = 0; i document.write(arr[i] + ' '); document.write(''); } let arr = [ 10, 5, 3, 2, 4 ]; let n = arr.length; n = deleteRoot(arr, n); printArray(arr, n); // This code is contributed by divyeshrabdiya07.>
파이썬3
# Python 3 program for implement deletion in Heaps># To heapify a subtree rooted with node i which is># an index of arr[] and n is the size of heap>def>heapify(arr, n, i):>>largest>=>i>#Initialize largest as root>>l>=>2>*>i>+>1># left = 2*i + 1>>r>=>2>*>i>+>2># right = 2*i + 2>>#If left child is larger than root>>if>(l and arr[l]>arr[largest]): maximum = l # 오른쪽 자식이 지금까지의 maximum보다 큰 경우 if (r and arr[r]> arr[largest]): maximum = r # maximum이 루트가 아닌 경우 if (largest != i) : arr[i],arr[largest]=arr[largest],arr[i] # 영향을 받은 하위 트리를 재귀적으로 힙화합니다. heapify(arr, n, maximum) # 힙에서 루트를 삭제하는 함수 def deleteRoot(arr): global n # 마지막 요소를 가져옵니다. lastElement = arr[n - 1] # 루트를 마지막 요소로 교체 arr[0] = lastElement # 힙 크기를 1만큼 줄입니다. n = n - 1 # 루트 노드를 힙화합니다 heapify(arr, n, 0) # n 크기의 배열을 인쇄하는 유틸리티 함수 def printArray(arr, n): for i in range(n): print(arr[i],end=' ') print() # 드라이버 코드 if __name__ == '__main__': # 최대 힙의 배열 표현 # 10 # / # 5 3 # / # 2 4 arr = [ 10, 5, 3, 2, 4 ] n = len(arr) deleteRoot( arr) printArray(arr, n) # 이 코드는 Rajat Kumar가 제공한 것입니다.>
산출
5 4 3 2시간 복잡도 : O(log n) 여기서 n은 힙에 요소가 없습니다.
보조 공간: 에)삼. Max-heap 데이터 구조에 대한 Peek 작업:
최대 요소(즉, 힙의 루트)에 액세스하려면 루트 노드의 값이 반환됩니다. 최대 힙에서 엿보기의 시간 복잡도는 O(1)입니다.
최대 힙의 피크 요소
Max-Heap에서 Peek 작업 구현:
C++
#include>#include>int>main() {>>// Create a max heap with some elements using a priority_queue>>std::priority_queue <>int>>최대힙;>>maxHeap.push(9);>>maxHeap.push(8);>>maxHeap.push(7);>>maxHeap.push(6);>>maxHeap.push(5);>>maxHeap.push(4);>>maxHeap.push(3);>>maxHeap.push(2);>>maxHeap.push(1);>>// Get the peak element (i.e., the largest element)>>int>peakElement = maxHeap.top();>>// Print the peak element>>std::cout < <>'Peak element: '>< < peakElement < < std::endl;>>return>0;>}>
자바
import>java.util.PriorityQueue;>public>class>GFG {>>public>static>void>main(String[] args) {>>// Create a max heap with some elements using a PriorityQueue>>PriorityQueue maxHeap =>new>PriorityQueue((a, b) ->b-a);>>maxHeap.add(>9>);>>maxHeap.add(>8>);>>maxHeap.add(>7>);>>maxHeap.add(>6>);>>maxHeap.add(>5>);>>maxHeap.add(>4>);>>maxHeap.add(>3>);>>maxHeap.add(>2>);>>maxHeap.add(>1>);>>// Get the peak element (i.e., the largest element)>>int>peakElement = maxHeap.peek();>>// Print the peak element>>System.out.println(>'Peak element: '>+ peakElement);>>}>}>
씨#
using>System;>using>System.Collections.Generic;>public>class>GFG {>>public>static>void>Main() {>>// Create a min heap with some elements using a PriorityQueue>>var>maxHeap =>new>PriorityQueue <>int>>();>>maxHeap.Enqueue(9);>>maxHeap.Enqueue(8);>>maxHeap.Enqueue(7);>>maxHeap.Enqueue(6);>>maxHeap.Enqueue(5);>>maxHeap.Enqueue(4);>>maxHeap.Enqueue(3);>>maxHeap.Enqueue(2);>>maxHeap.Enqueue(1);>>// Get the peak element (i.e., the smallest element)>>int>peakElement = maxHeap.Peek();>>// Print the peak element>>Console.WriteLine(>'Peak element: '>+ peakElement);>>}>}>// Define a PriorityQueue class that uses a max heap>class>PriorityQueue>where>T : IComparable {>>private>List heap;>>public>PriorityQueue() {>>this>.heap =>new>List();>>}>>public>int>Count {>>get>{>return>this>.heap.Count; }>>}>>public>void>Enqueue(T item) {>>this>.heap.Add(item);>>this>.BubbleUp(>this>.heap.Count - 1);>>}>>public>T Dequeue() {>>T item =>this>.heap[0];>>int>lastIndex =>this>.heap.Count - 1;>>this>.heap[0] =>this>.heap[lastIndex];>>this>.heap.RemoveAt(lastIndex);>>this>.BubbleDown(0);>>return>item;>>}>>public>T Peek() {>>return>this>.heap[0];>>}>>private>void>BubbleUp(>int>index) {>>while>(index>0) {>>int>parentIndex = (index - 1) / 2;>>if>(>this>.heap[parentIndex].CompareTo(>this>.heap[index])>= 0) {>>break>;>>}>>Swap(parentIndex, index);>>index = parentIndex;>>}>>}>>private>void>BubbleDown(>int>index) {>>while>(index <>this>.heap.Count) {>>int>leftChildIndex = index * 2 + 1;>>int>rightChildIndex = index * 2 + 2;>>int>largestChildIndex = index;>>if>(leftChildIndex <>this>.heap.Count &&>this>.heap[leftChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {>>largestChildIndex = leftChildIndex;>>}>>if>(rightChildIndex <>this>.heap.Count &&>this>.heap[rightChildIndex].CompareTo(>this>.heap[largestChildIndex])>0) {>>largestChildIndex = rightChildIndex;>>}>>if>(largestChildIndex == index) {>>break>;>>}>>Swap(largestChildIndex, index);>>index = largestChildIndex;>>}>>}>>private>void>Swap(>int>i,>int>j) {>>T temp =>this>.heap[i];>>this>.heap[i] =>this>.heap[j];>>this>.heap[j] = temp;>>}>}>
자바스크립트
// Define a MaxHeap class that uses an array>class MaxHeap {>>constructor() {>>this>.heap = [];>>}>>push(item) {>>this>.heap.push(item);>>this>.bubbleUp(>this>.heap.length - 1);>>}>>pop() {>>let item =>this>.heap[0];>>let lastIndex =>this>.heap.length - 1;>>this>.heap[0] =>this>.heap[lastIndex];>>this>.heap.pop();>>this>.bubbleDown(0);>>return>item;>>}>>peak() {>>return>this>.heap[0];>>}>>bubbleUp(index) {>>while>(index>0) {>>let parentIndex = Math.floor((index - 1) / 2);>>if>(>this>.heap[parentIndex]>=>this>.heap[index]) {>>break>;>>}>>this>.swap(parentIndex, index);>>index = parentIndex;>>}>>}>>bubbleDown(index) {>>while>(index <>this>.heap.length) {>>let leftChildIndex = index * 2 + 1;>>let rightChildIndex = index * 2 + 2;>>let largestChildIndex = index;>>if>(leftChildIndex <>this>.heap.length &&>this>.heap[leftChildIndex]>>this>.heap[largestChildIndex]) {>>largestChildIndex = leftChildIndex;>>}>>if>(rightChildIndex <>this>.heap.length &&>this>.heap[rightChildIndex]>>this>.heap[largestChildIndex]) {>>largestChildIndex = rightChildIndex;>>}>>if>(largestChildIndex === index) {>>break>;>>}>>this>.swap(largestChildIndex, index);>>index = largestChildIndex;>>}>>}>>swap(i, j) {>>let temp =>this>.heap[i];>>this>.heap[i] =>this>.heap[j];>>this>.heap[j] = temp;>>}>}>// Create a max heap with some elements using an array>let maxHeap =>new>MaxHeap();>maxHeap.push(9);>maxHeap.push(8);>maxHeap.push(7);>maxHeap.push(6);>maxHeap.push(5);>maxHeap.push(4);>maxHeap.push(3);>maxHeap.push(2);>maxHeap.push(1);>// Get the peak element (i.e., the largest element)>let peakElement = maxHeap.peak();>// Print the peak element>console.log(>'Peak element: '>+ peakElement);>
파이썬3
import>heapq># Create a max heap with some elements using a list>max_heap>=>[>1>,>2>,>3>,>4>,>5>,>6>,>7>,>8>,>9>]>heapq.heapify(max_heap)># Get the peak element (i.e., the largest element)>peak_element>=>heapq.nlargest(>1>, max_heap)[>0>]># Print the peak element>print>(>'Peak element:'>, peak_element)>
산출
Peak element: 9시간 복잡도 :
- 다음을 사용하여 구현된 최대 힙에서 정렬 또는 목록인 경우 피크 요소는 항상 힙의 루트에 위치하므로 상수 시간 O(1)에 액세스할 수 있습니다.
- 다음을 사용하여 구현된 최대 힙에서 이진 트리 , 피크 요소는 항상 트리의 루트에 위치하므로 O(1) 시간 내에 액세스할 수도 있습니다.
보조 공간: 에)
4. Max-heap 데이터 구조에 대한 Heapify 작업 :
heapify 작업을 사용하면 정렬되지 않은 배열에서 최대 힙을 생성할 수 있습니다. 이는 리프가 아닌 마지막 노드에서 시작하여 모든 노드가 힙 속성을 충족할 때까지 버블다운 작업을 반복적으로 수행하여 수행됩니다. 최대 힙에서 heapify의 시간 복잡도는 O(n)입니다.
Max-Heap에서 Heapify 작업
5. Max-heap 데이터 구조에 대한 검색 작업 :
최대 힙에서 요소를 검색하려면 힙을 나타내는 배열에 대해 선형 검색을 수행할 수 있습니다. 그러나 선형 탐색의 시간 복잡도는 O(n)이므로 효율적이지 않습니다. 따라서 검색은 최대 힙에서 일반적으로 사용되는 작업이 아닙니다.
다음은 다음을 사용하여 최대 힙에서 요소를 검색하는 방법을 보여주는 예제 코드입니다. 표준::찾기() :
C++
#include>#include // for std::priority_queue>using>namespace>std;>int>main() {>>std::priority_queue <>int>>최대_힙;>>// example max heap>>>max_heap.push(10);>>max_heap.push(9);>>max_heap.push(8);>>max_heap.push(6);>>max_heap.push(4);>>int>element = 6;>// element to search for>>bool>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>std::priority_queue <>int>>임시 = max_heap;>>while>(!temp.empty()) {>>if>(temp.top() == element) {>>found =>true>;>>break>;>>}>>temp.pop();>>}>>if>(found) {>>std::cout < <>'Element found in the max heap.'>< < std::endl;>>}>else>{>>std::cout < <>'Element not found in the max heap.'>< < std::endl;>>}>>return>0;>}>
자바
import>java.util.PriorityQueue;>public>class>GFG {>>public>static>void>main(String[] args) {>>PriorityQueue maxHeap =>new>PriorityQueue((a, b) ->b-a);>>maxHeap.add(>3>);>// insert elements into the priority queue>>maxHeap.offer(>1>);>>maxHeap.offer(>4>);>>maxHeap.offer(>1>);>>maxHeap.offer(>6>);>>int>element =>6>;>// element to search for>>boolean>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>PriorityQueue temp =>new>PriorityQueue(maxHeap);>>while>(!temp.isEmpty()) {>>if>(temp.poll() == element) {>>found =>true>;>>break>;>>}>>}>>if>(found) {>>System.out.println(>'Element found in the max heap.'>);>>}>else>{>>System.out.println(>'Element not found in the max heap.'>);>>}>>}>}>
씨#
using>System;>using>System.Collections.Generic;>class>Program {>>static>void>Main(>string>[] args) {>>// Create a max heap with some elements using a PriorityQueue>>PriorityQueue <>int>>최대힙 =>new>PriorityQueue <>int>>();>>maxHeap.Enqueue(10);>>maxHeap.Enqueue(9);>>maxHeap.Enqueue(8);>>maxHeap.Enqueue(6);>>maxHeap.Enqueue(4);>>int>element = 6;>// element to search for>>bool>found =>false>;>>// Copy the max heap to a temporary queue and search for the element>>PriorityQueue <>int>>온도 =>new>PriorityQueue <>int>>(최대힙);>>while>(temp.Count>0) {>>if>(temp.Peek() == element) {>>found =>true>;>>break>;>>}>>temp.Dequeue();>>}>>if>(found) {>>Console.WriteLine(>'Element found in the max heap.'>);>>}>else>{>>Console.WriteLine(>'Element not found in the max heap.'>);>>}>>}>}>// PriorityQueue class>class>PriorityQueue>where>T : IComparable {>>private>List heap =>new>List();>>public>void>Enqueue(T item) {>>heap.Add(item);>>int>child = heap.Count - 1;>>while>(child>0) {>>int>parent = (child - 1) / 2;>>if>(heap[child].CompareTo(heap[parent])>0) {>>T tmp = heap[child];>>heap[child] = heap[parent];>>heap[parent] = tmp;>>child = parent;>>}>else>{>>break>;>>}>>}>>}>>public>T Dequeue() {>>int>last = heap.Count - 1;>>T frontItem = heap[0];>>heap[0] = heap[last];>>heap.RemoveAt(last);>>last--;>>int>parent = 0;>>while>(>true>) {>>int>leftChild = parent * 2 + 1;>>if>(leftChild>마지막) {>>break>;>>}>>int>rightChild = leftChild + 1;>>if>(rightChild <= last && heap[leftChild].CompareTo(heap[rightChild]) < 0) {>>leftChild = rightChild;>>}>>if>(heap[parent].CompareTo(heap[leftChild]) <0) {>>T tmp = heap[parent];>>heap[parent] = heap[leftChild];>>heap[leftChild] = tmp;>>parent = leftChild;>>}>else>{>>break>;>>}>>}>>return>frontItem;>>}>>public>T Peek() {>>return>heap[0];>>}>>public>int>Count {>>get>{>>return>heap.Count;>>}>>}>}>
자바스크립트
const maxHeap =>new>PriorityQueue((a, b) =>b-a);>maxHeap.add(3);>// insert elements into the priority queue>maxHeap.add(1);>maxHeap.add(4);>maxHeap.add(1);>maxHeap.add(6);>const element = 6;>// element to search for>let found =>false>;>// Copy the max heap to a temporary queue and search for the element>const temp =>new>PriorityQueue(maxHeap);>while>(!temp.isEmpty()) {>if>(temp.poll() === element) {>found =>true>;>break>;>}>}>if>(found) {>console.log(>'Element found in the max heap.'>);>}>else>{>console.log(>'Element not found in the max heap.'>);>}>
파이썬3
import>heapq>max_heap>=>[>10>,>8>,>7>,>6>,>5>,>3>,>2>,>1>]># example max heap>heapq._heapify_max(max_heap)>element>=>6># element to search for>found>=>False># Copy the max heap to a temporary list and search for the element>temp>=>list>(max_heap)>while>temp:>>if>heapq._heappop_max(temp)>=>=>element:>>found>=>True>>break>if>found:>>print>(>'Element found in the max heap.'>)>else>:>>print>(>'Element not found in the max heap.'>)>
산출
Element found in the max heap.시간 복잡도 : O(n), 여기서 n은 힙의 크기입니다.
보조 공간 : 에),Max-Heap 데이터 구조의 응용:
- 힙 정렬 알고리즘: 힙 데이터 구조는 최악의 경우 시간 복잡도가 O(n log n)인 효율적인 정렬 알고리즘인 힙 정렬 알고리즘의 기초입니다. 힙 정렬 알고리즘은 데이터베이스 인덱싱 및 수치 분석을 포함한 다양한 응용 프로그램에 사용됩니다.
- 메모리 관리: 힙 데이터 구조는 메모리 관리 시스템에서 메모리를 동적으로 할당하고 할당 해제하는 데 사용됩니다. 힙은 메모리 블록을 저장하는 데 사용되며, 힙 데이터 구조는 메모리 블록을 효율적으로 관리하고 필요에 따라 프로그램에 할당하는 데 사용됩니다.
- 그래프 알고리즘: 힙 데이터 구조는 Dijkstra 알고리즘, Prim 알고리즘, Kruskal 알고리즘 등 다양한 그래프 알고리즘에 사용됩니다. 이러한 알고리즘에는 효율적인 우선순위 큐 구현이 필요하며 이는 힙 데이터 구조를 사용하여 달성할 수 있습니다.
- 작업 일정: 힙 데이터 구조는 작업 예약 알고리즘에 사용되며, 여기서 작업은 우선 순위나 기한을 기준으로 예약됩니다. 힙 데이터 구조를 사용하면 우선순위가 가장 높은 작업에 효율적으로 액세스할 수 있으므로 작업 스케줄링 애플리케이션에 유용한 데이터 구조가 됩니다.
Max-Heap 데이터 구조의 장점:
- 최대값을 효율적으로 유지합니다. 최대 힙을 사용하면 힙의 최대 요소에 지속적으로 액세스할 수 있으므로 최대 요소를 빠르게 찾아야 하는 애플리케이션에 유용합니다.
- 효율적인 삽입 및 삭제 작업: 최대 힙의 삽입 및 삭제 작업은 O(log n)의 시간 복잡도를 가지므로 대규모 요소 컬렉션에 효율적입니다.
- 우선순위 대기열: 최대 힙은 작업 스케줄링, 작업 우선순위 지정 및 이벤트 기반 시뮬레이션과 같은 많은 애플리케이션에 유용한 우선순위 큐를 구현하는 데 사용될 수 있습니다.
- 정렬: 최대 힙은 O(n log n)의 최악의 시간 복잡도를 갖는 효율적인 정렬 알고리즘인 힙 정렬을 구현하는 데 사용될 수 있습니다.
- 공간 효율성: 최대 힙은 배열로 구현될 수 있으며 이진 검색 트리나 연결 목록과 같은 다른 데이터 구조에 비해 메모리가 덜 필요합니다.
최대 힙 데이터 구조는 특히 최대 요소에 빠르게 액세스해야 하거나 요소를 정렬하거나 우선순위를 지정해야 하는 경우 요소 컬렉션을 유지 관리하고 조작하는 데 유용하고 효율적인 도구입니다.
