ㅏ 바이너리 힙 는 완전한 이진 트리 이는 구조를 기반으로 최대 또는 최소 요소를 얻기 위해 데이터를 효율적으로 저장하는 데 사용됩니다.
바이너리 힙은 최소 힙 또는 최대 힙입니다. 최소 바이너리 힙에서 루트의 키는 바이너리 힙에 있는 모든 키 중에서 최소값이어야 합니다. 이진 트리의 모든 노드에 대해 동일한 속성이 반복적으로 true여야 합니다. 최대 바이너리 힙은 MinHeap과 유사합니다.
최소 힙의 예:
10 10
/ /
20 100 15 30
/ / /
30 40 50 100 40
바이너리 힙은 어떻게 표현되나요?
바이너리 힙은 완전한 이진 트리 . 바이너리 힙은 일반적으로 배열로 표현됩니다.
- 루트 요소는 Arr[0]에 있습니다.
- 아래 표는 i에 대한 다른 노드의 인덱스를 보여줍니다.일노드, 즉 Arr[i]:
| 도착[(i-1)/2] | 상위 노드를 반환합니다. |
| 도착[(2*i)+1] | 왼쪽 자식 노드를 반환합니다. |
| 도착[(2*i)+2] | 올바른 자식 노드를 반환합니다. |
배열 표현을 달성하기 위해 사용되는 순회 방법은 다음과 같습니다. 레벨 순서 순회 . 참고하세요 바이너리 힙의 배열 표현 자세한 내용은.
힙 작업:
다음은 최소 힙에 대한 몇 가지 표준 작업입니다.
- getMin(): Min Heap의 루트 요소를 반환합니다. 이 작업의 시간 복잡도는 오(1) . 최대힙의 경우에는 다음과 같습니다. getMax() .
- 추출최소() : MinHeap에서 최소 요소를 제거합니다. 이 작업의 시간 복잡도는 오(로그 N) 이 작업은 힙 속성을 유지해야 하기 때문에(호출하여) 힙파이() ) 뿌리를 제거한 후.
- 감소키() : 키 값을 감소시킵니다. 이 연산의 시간복잡도는 오(로그 N) . 노드의 감소된 키 값이 해당 노드의 상위 값보다 크면 아무 작업도 수행할 필요가 없습니다. 그렇지 않으면 위반된 힙 속성을 수정하기 위해 위로 순회해야 합니다.
- 끼워 넣다() : 새 키를 삽입하려면 다음이 필요합니다. 오(로그 N) 시간. 트리 끝에 새 키를 추가합니다. 새 키가 상위 키보다 크면 아무 작업도 수행할 필요가 없습니다. 그렇지 않으면 위반된 힙 속성을 수정하기 위해 위로 순회해야 합니다.
- 삭제() : 키를 삭제하는 데도 시간이 걸립니다. 오(로그 N) 시간. 호출하여 삭제할 키를 최소 무한값으로 바꿉니다. 감소키() . 감소키() 이후 마이너스 무한 값은 루트에 도달해야 하므로 호출합니다. 추출최소() 열쇠를 제거하려면.
다음은 기본 힙 작업의 구현입니다.
C++
// A C++ program to demonstrate common Binary Heap Operations> #include> #include> using> namespace> std;> > // Prototype of a utility function to swap two integers> void> swap(>int> *x,>int> *y);> > // A class for Min Heap> class> MinHeap> {> >int> *harr;>// pointer to array of elements in heap> >int> capacity;>// maximum possible size of min heap> >int> heap_size;>// Current number of elements in min heap> public>:> >// Constructor> >MinHeap(>int> capacity);> > >// to heapify a subtree with the root at given index> >void> MinHeapify(>int> i);> > >int> parent(>int> i) {>return> (i-1)/2; }> > >// to get index of left child of node at index i> >int> left(>int> i) {>return> (2*i + 1); }> > >// to get index of right child of node at index i> >int> right(>int> i) {>return> (2*i + 2); }> > >// to extract the root which is the minimum element> >int> extractMin();> > >// Decreases key value of key at index i to new_val> >void> decreaseKey(>int> i,>int> new_val);> > >// Returns the minimum key (key at root) from min heap> >int> getMin() {>return> harr[0]; }> > >// Deletes a key stored at index i> >void> deleteKey(>int> i);> > >// Inserts a new key 'k'> >void> insertKey(>int> k);> };> > // Constructor: Builds a heap from a given array a[] of given size> MinHeap::MinHeap(>int> cap)> {> >heap_size = 0;> >capacity = cap;> >harr =>new> int>[cap];> }> > // Inserts a new key 'k'> void> MinHeap::insertKey(>int> k)> {> >if> (heap_size == capacity)> >{> >cout <<>'
Overflow: Could not insertKey
'>;> >return>;> >}> > >// First insert the new key at the end> >heap_size++;> >int> i = heap_size - 1;> >harr[i] = k;> > >// Fix the min heap property if it is violated> >while> (i != 0 && harr[parent(i)]>Harr[i])> >{> >swap(&harr[i], &harr[parent(i)]);> >i = parent(i);> >}> }> > // Decreases value of key at index 'i' to new_val. It is assumed that> // new_val is smaller than harr[i].> void> MinHeap::decreaseKey(>int> i,>int> new_val)> {> >harr[i] = new_val;> >while> (i != 0 && harr[parent(i)]>Harr[i])> >{> >swap(&harr[i], &harr[parent(i)]);> >i = parent(i);> >}> }> > // Method to remove minimum element (or root) from min heap> int> MinHeap::extractMin()> {> >if> (heap_size <= 0)> >return> INT_MAX;> >if> (heap_size == 1)> >{> >heap_size--;> >return> harr[0];> >}> > >// Store the minimum value, and remove it from heap> >int> root = harr[0];> >harr[0] = harr[heap_size-1];> >heap_size--;> >MinHeapify(0);> > >return> root;> }> > > // This function deletes key at index i. It first reduced value to minus> // infinite, then calls extractMin()> void> MinHeap::deleteKey(>int> i)> {> >decreaseKey(i, INT_MIN);> >extractMin();> }> > // A recursive method to heapify a subtree with the root at given index> // This method assumes that the subtrees are already heapified> void> MinHeap::MinHeapify(>int> i)> {> >int> l = left(i);> >int> r = right(i);> >int> smallest = i;> >if> (l smallest = l; if (r smallest = r; if (smallest != i) { swap(&harr[i], &harr[smallest]); MinHeapify(smallest); } } // A utility function to swap two elements void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } // Driver program to test above functions int main() { MinHeap h(11); h.insertKey(3); h.insertKey(2); h.deleteKey(1); h.insertKey(15); h.insertKey(5); h.insertKey(4); h.insertKey(45); cout << h.extractMin() << ' '; cout << h.getMin() << ' '; h.decreaseKey(2, 1); cout << h.getMin(); return 0; }> |
>
>
음악 다운로드 방법
자바
// Java program for the above approach> import> java.util.*;> > // A class for Min Heap> class> MinHeap {> > >// To store array of elements in heap> >private> int>[] heapArray;> > >// max size of the heap> >private> int> capacity;> > >// Current number of elements in the heap> >private> int> current_heap_size;> > >// Constructor> >public> MinHeap(>int> n) {> >capacity = n;> >heapArray =>new> int>[capacity];> >current_heap_size =>0>;> >}> > >// Swapping using reference> >private> void> swap(>int>[] arr,>int> a,>int> b) {> >int> temp = arr[a];> >arr[a] = arr[b];> >arr[b] = temp;> >}> > > >// Get the Parent index for the given index> >private> int> parent(>int> key) {> >return> (key ->1>) />2>;> >}> > >// Get the Left Child index for the given index> >private> int> left(>int> key) {> >return> 2> * key +>1>;> >}> > >// Get the Right Child index for the given index> >private> int> right(>int> key) {> >return> 2> * key +>2>;> >}> > > >// Inserts a new key> >public> boolean> insertKey(>int> key) {> >if> (current_heap_size == capacity) {> > >// heap is full> >return> false>;> >}> > >// First insert the new key at the end> >int> i = current_heap_size;> >heapArray[i] = key;> >current_heap_size++;> > >// Fix the min heap property if it is violated> >while> (i !=>0> && heapArray[i] swap(heapArray, i, parent(i)); i = parent(i); } return true; } // Decreases value of given key to new_val. // It is assumed that new_val is smaller // than heapArray[key]. public void decreaseKey(int key, int new_val) { heapArray[key] = new_val; while (key != 0 && heapArray[key] swap(heapArray, key, parent(key)); key = parent(key); } } // Returns the minimum key (key at // root) from min heap public int getMin() { return heapArray[0]; } // Method to remove minimum element // (or root) from min heap public int extractMin() { if (current_heap_size <= 0) { return Integer.MAX_VALUE; } if (current_heap_size == 1) { current_heap_size--; return heapArray[0]; } // Store the minimum value, // and remove it from heap int root = heapArray[0]; heapArray[0] = heapArray[current_heap_size - 1]; current_heap_size--; MinHeapify(0); return root; } // This function deletes key at the // given index. It first reduced value // to minus infinite, then calls extractMin() public void deleteKey(int key) { decreaseKey(key, Integer.MIN_VALUE); extractMin(); } // A recursive method to heapify a subtree // with the root at given index // This method assumes that the subtrees // are already heapified private void MinHeapify(int key) { int l = left(key); int r = right(key); int smallest = key; if (l smallest = l; } if (r smallest = r; } if (smallest != key) { swap(heapArray, key, smallest); MinHeapify(smallest); } } // Increases value of given key to new_val. // It is assumed that new_val is greater // than heapArray[key]. // Heapify from the given key public void increaseKey(int key, int new_val) { heapArray[key] = new_val; MinHeapify(key); } // Changes value on a key public void changeValueOnAKey(int key, int new_val) { if (heapArray[key] == new_val) { return; } if (heapArray[key] increaseKey(key, new_val); } else { decreaseKey(key, new_val); } } } // Driver Code class MinHeapTest { public static void main(String[] args) { MinHeap h = new MinHeap(11); h.insertKey(3); h.insertKey(2); h.deleteKey(1); h.insertKey(15); h.insertKey(5); h.insertKey(4); h.insertKey(45); System.out.print(h.extractMin() + ' '); System.out.print(h.getMin() + ' '); h.decreaseKey(2, 1); System.out.print(h.getMin()); } } // This code is contributed by rishabmalhdijo> |
>
>
파이썬
# A Python program to demonstrate common binary heap operations> > # Import the heap functions from python library> from> heapq>import> heappush, heappop, heapify> > # heappop - pop and return the smallest element from heap> # heappush - push the value item onto the heap, maintaining> # heap invarient> # heapify - transform list into heap, in place, in linear time> > # A class for Min Heap> class> MinHeap:> > ># Constructor to initialize a heap> >def> __init__(>self>):> >self>.heap>=> []> > >def> parent(>self>, i):> >return> (i>->1>)>/>2> > ># Inserts a new key 'k'> >def> insertKey(>self>, k):> >heappush(>self>.heap, k)> > ># Decrease value of key at index 'i' to new_val> ># It is assumed that new_val is smaller than heap[i]> >def> decreaseKey(>self>, i, new_val):> >self>.heap[i]>=> new_val> >while>(i !>=> 0> and> self>.heap[>self>.parent(i)]>>self>.heap[i]):> ># Swap heap[i] with heap[parent(i)]> >self>.heap[i] ,>self>.heap[>self>.parent(i)]>=> (> >self>.heap[>self>.parent(i)],>self>.heap[i])> > ># Method to remove minimum element from min heap> >def> extractMin(>self>):> >return> heappop(>self>.heap)> > ># This function deletes key at index i. It first reduces> ># value to minus infinite and then calls extractMin()> >def> deleteKey(>self>, i):> >self>.decreaseKey(i,>float>(>'-inf'>))> >self>.extractMin()> > ># Get the minimum element from the heap> >def> getMin(>self>):> >return> self>.heap[>0>]> > # Driver pgoratm to test above function> heapObj>=> MinHeap()> heapObj.insertKey(>3>)> heapObj.insertKey(>2>)> heapObj.deleteKey(>1>)> heapObj.insertKey(>15>)> heapObj.insertKey(>5>)> heapObj.insertKey(>4>)> heapObj.insertKey(>45>)> > print> heapObj.extractMin(),> print> heapObj.getMin(),> heapObj.decreaseKey(>2>,>1>)> print> heapObj.getMin()> > # This code is contributed by Nikhil Kumar Singh(nickzuck_007)> |
최대 절전 모드란 무엇인가요?
>
>
씨#
// C# program to demonstrate common> // Binary Heap Operations - Min Heap> using> System;> > // A class for Min Heap> class> MinHeap{> > // To store array of elements in heap> public> int>[] heapArray{>get>;>set>; }> > // max size of the heap> public> int> capacity{>get>;>set>; }> > // Current number of elements in the heap> public> int> current_heap_size{>get>;>set>; }> > // Constructor> public> MinHeap(>int> n)> {> >capacity = n;> >heapArray =>new> int>[capacity];> >current_heap_size = 0;> }> > // Swapping using reference> public> static> void> Swap(>ref> T lhs,>ref> T rhs)> {> >T temp = lhs;> >lhs = rhs;> >rhs = temp;> }> > // Get the Parent index for the given index> public> int> Parent(>int> key)> {> >return> (key - 1) / 2;> }> > // Get the Left Child index for the given index> public> int> Left(>int> key)> {> >return> 2 * key + 1;> }> > // Get the Right Child index for the given index> public> int> Right(>int> key)> {> >return> 2 * key + 2;> }> > // Inserts a new key> public> bool> insertKey(>int> key)> {> >if> (current_heap_size == capacity)> >{> > >// heap is full> >return> false>;> >}> > >// First insert the new key at the end> >int> i = current_heap_size;> >heapArray[i] = key;> >current_heap_size++;> > >// Fix the min heap property if it is violated> >while> (i != 0 && heapArray[i] <> >heapArray[Parent(i)])> >{> >Swap(>ref> heapArray[i],> >ref> heapArray[Parent(i)]);> >i = Parent(i);> >}> >return> true>;> }> > // Decreases value of given key to new_val.> // It is assumed that new_val is smaller> // than heapArray[key].> public> void> decreaseKey(>int> key,>int> new_val)> {> >heapArray[key] = new_val;> > >while> (key != 0 && heapArray[key] <> >heapArray[Parent(key)])> >{> >Swap(>ref> heapArray[key],> >ref> heapArray[Parent(key)]);> >key = Parent(key);> >}> }> > // Returns the minimum key (key at> // root) from min heap> public> int> getMin()> {> >return> heapArray[0];> }> > // Method to remove minimum element> // (or root) from min heap> public> int> extractMin()> {> >if> (current_heap_size <= 0)> >{> >return> int>.MaxValue;> >}> > >if> (current_heap_size == 1)> >{> >current_heap_size--;> >return> heapArray[0];> >}> > >// Store the minimum value,> >// and remove it from heap> >int> root = heapArray[0];> > >heapArray[0] = heapArray[current_heap_size - 1];> >current_heap_size--;> >MinHeapify(0);> > >return> root;> }> > // This function deletes key at the> // given index. It first reduced value> // to minus infinite, then calls extractMin()> public> void> deleteKey(>int> key)> {> >decreaseKey(key,>int>.MinValue);> >extractMin();> }> > // A recursive method to heapify a subtree> // with the root at given index> // This method assumes that the subtrees> // are already heapified> public> void> MinHeapify(>int> key)> {> >int> l = Left(key);> >int> r = Right(key);> > >int> smallest = key;> >if> (l heapArray[l] { smallest = l; } if (r heapArray[r] { smallest = r; } if (smallest != key) { Swap(ref heapArray[key], ref heapArray[smallest]); MinHeapify(smallest); } } // Increases value of given key to new_val. // It is assumed that new_val is greater // than heapArray[key]. // Heapify from the given key public void increaseKey(int key, int new_val) { heapArray[key] = new_val; MinHeapify(key); } // Changes value on a key public void changeValueOnAKey(int key, int new_val) { if (heapArray[key] == new_val) { return; } if (heapArray[key] { increaseKey(key, new_val); } else { decreaseKey(key, new_val); } } } static class MinHeapTest{ // Driver code public static void Main(string[] args) { MinHeap h = new MinHeap(11); h.insertKey(3); h.insertKey(2); h.deleteKey(1); h.insertKey(15); h.insertKey(5); h.insertKey(4); h.insertKey(45); Console.Write(h.extractMin() + ' '); Console.Write(h.getMin() + ' '); h.decreaseKey(2, 1); Console.Write(h.getMin()); } } // This code is contributed by // Dinesh Clinton Albert(dineshclinton)> |
>
>
자바스크립트
자바 추상 클래스
// A class for Min Heap> class MinHeap> {> >// Constructor: Builds a heap from a given array a[] of given size> >constructor()> >{> >this>.arr = [];> >}> > >left(i) {> >return> 2*i + 1;> >}> > >right(i) {> >return> 2*i + 2;> >}> > >parent(i){> >return> Math.floor((i - 1)/2)> >}> > >getMin()> >{> >return> this>.arr[0]> >}> > >insert(k)> >{> >let arr =>this>.arr;> >arr.push(k);> > >// Fix the min heap property if it is violated> >let i = arr.length - 1;> >while> (i>0 && 도착[>this>.parent(i)]>도착[i])> >{> >let p =>this>.parent(i);> >[arr[i], arr[p]] = [arr[p], arr[i]];> >i = p;> >}> >}> > >// Decreases value of key at index 'i' to new_val.> >// It is assumed that new_val is smaller than arr[i].> >decreaseKey(i, new_val)> >{> >let arr =>this>.arr;> >arr[i] = new_val;> > >while> (i !== 0 && arr[>this>.parent(i)]>도착[i])> >{> >let p =>this>.parent(i);> >[arr[i], arr[p]] = [arr[p], arr[i]];> >i = p;> >}> >}> > >// Method to remove minimum element (or root) from min heap> >extractMin()> >{> >let arr =>this>.arr;> >if> (arr.length == 1) {> >return> arr.pop();> >}> > >// Store the minimum value, and remove it from heap> >let res = arr[0];> >arr[0] = arr[arr.length-1];> >arr.pop();> >this>.MinHeapify(0);> >return> res;> >}> > > >// This function deletes key at index i. It first reduced value to minus> >// infinite, then calls extractMin()> >deleteKey(i)> >{> >this>.decreaseKey(i,>this>.arr[0] - 1);> >this>.extractMin();> >}> > >// A recursive method to heapify a subtree with the root at given index> >// This method assumes that the subtrees are already heapified> >MinHeapify(i)> >{> >let arr =>this>.arr;> >let n = arr.length;> >if> (n === 1) {> >return>;> >}> >let l =>this>.left(i);> >let r =>this>.right(i);> >let smallest = i;> >if> (l smallest = l; if (r smallest = r; if (smallest !== i) { [arr[i], arr[smallest]] = [arr[smallest], arr[i]] this.MinHeapify(smallest); } } } let h = new MinHeap(); h.insert(3); h.insert(2); h.deleteKey(1); h.insert(15); h.insert(5); h.insert(4); h.insert(45); console.log(h.extractMin() + ' '); console.log(h.getMin() + ' '); h.decreaseKey(2, 1); console.log(h.extractMin());> |
>
>산출
2 4 1>
힙의 응용:
- 힙 정렬 : Heap Sort는 Binary Heap을 사용하여 O(nLogn) 시간에 배열을 정렬합니다.
- 우선순위 대기열: 우선순위 큐는 O(log N) 시간에 insert(), delete(), extractmax(), 감소키() 연산을 지원하므로 Binary Heap을 사용하여 효율적으로 구현할 수 있습니다. 이항 힙과 피보나치 힙은 이진 힙의 변형입니다. 이러한 변형은 결합도 효율적으로 수행합니다.
- 그래프 알고리즘: 우선순위 대기열은 특히 다음과 같은 그래프 알고리즘에 사용됩니다. Dijkstra의 최단 경로 그리고 Prim의 최소 스패닝 트리 .
- 힙을 사용하면 많은 문제를 효율적으로 해결할 수 있습니다. 예를 들어 다음을 참조하세요. ㅏ) 배열에서 K번째로 큰 요소 . 비) 거의 정렬된 배열 정렬/ 씨) K개의 정렬된 배열 병합 .
관련된 링크들:
- 힙 코딩 실습
- 힙에 관한 모든 기사
- PriorityQueue : Java 라이브러리의 바이너리 힙 구현