ㅏ 최대 힙 각 내부 노드의 값이 해당 노드의 하위 노드 값보다 크거나 같은 완전한 이진 트리입니다. 힙의 요소를 배열로 매핑하는 것은 간단합니다. 노드가 인덱스 k에 저장되면 왼쪽 자식은 인덱스 2k + 1에 저장되고 오른쪽 자식은 인덱스 2k + 2에 저장됩니다.
삽화: 최대 힙
최대 힙은 어떻게 표현되나요?
A-Max Heap은 완전한 이진 트리입니다. A-Max 힙은 일반적으로 배열로 표시됩니다. 루트 요소는 Arr[0]에 있습니다. 아래 표는 해당 노드에 대한 다른 노드의 인덱스를 보여줍니다. 그것 노드, 즉 Arr[i]:
Arr[(i-1)/2] 상위 노드를 반환합니다.
Arr[(2*i)+1] 왼쪽 자식 노드를 반환합니다.
Arr[(2*i)+2] 오른쪽 자식 노드를 반환합니다.삼항 연산자 자바
Max Heap에 대한 작업은 다음과 같습니다.
- getMax(): Max Heap의 루트 요소를 반환합니다. 이 작업의 시간 복잡도는 다음과 같습니다. 오(1) .
- 추출최대(): 에서 최대 요소를 제거합니다. 최대힙 . 이 작업의 시간 복잡도는 다음과 같습니다. O(로그n) 이 작업은 heapify() 메서드 뿌리를 제거한 후.
- 끼워 넣다(): 새 키를 삽입하려면 다음이 필요합니다. O(로그n) 시간. 트리 끝에 새 키를 추가합니다. 새 키가 상위 키보다 작으면 아무 작업도 수행할 필요가 없습니다. 그렇지 않으면 위반된 힙 속성을 수정하기 위해 위로 순회해야 합니다.
메모: 아래 구현에서는 구현을 단순화하기 위해 인덱스 1에서 인덱싱을 수행합니다.
행동 양식:
나열된 목표를 달성할 수 있는 두 가지 방법이 있습니다.
plsql
- 생성을 통한 기본 접근 방식 최대Heapify() 방법
- 사용 Collections.reverseOrder() 라이브러리 함수를 통한 방법
방법 1: 생성을 통한 기본 접근 방식 최대Heapify() 방법
왼쪽 및 오른쪽 하위 트리가 이미 힙화되어 있다고 가정하고 루트만 수정하면 되는 메서드를 생성할 것입니다.
예
자바
// Java program to implement Max Heap> // Main class> public> class> MaxHeap {> >private> int>[] Heap;> >private> int> size;> >private> int> maxsize;> >// Constructor to initialize an> >// empty max heap with given maximum> >// capacity> >public> MaxHeap(>int> maxsize)> >{> >// This keyword refers to current instance itself> >this>.maxsize = maxsize;> >this>.size =>0>;> >Heap =>new> int>[>this>.maxsize];> >}> >// Method 1> >// Returning position of parent> >private> int> parent(>int> pos) {>return> (pos ->1>) />2>; }> >// Method 2> >// Returning left children> >private> int> leftChild(>int> pos) {>return> (>2> * pos) +>1>; }> >// Method 3> >// Returning right children> >private> int> rightChild(>int> pos)> >{> >return> (>2> * pos) +>2>;> >}> >// Method 4> >// Returning true if given node is leaf> >private> boolean> isLeaf(>int> pos)> >{> >if> (pos>(사이즈 />2>) && pos <= size) {> >return> true>;> >}> >return> false>;> >}> >// Method 5> >// Swapping nodes> >private> void> swap(>int> fpos,>int> spos)> >{> >int> tmp;> >tmp = Heap[fpos];> >Heap[fpos] = Heap[spos];> >Heap[spos] = tmp;> >}> >// Method 6> >// Recursive function to max heapify given subtree> >private> void> maxHeapify(>int> pos)> >{> >if> (isLeaf(pos))> >return>;> >if> (Heap[pos] || Heap[pos] if (Heap[leftChild(pos)]>힙[rightChild(pos)]) { swap(pos, leftChild(pos)); maxHeapify(leftChild(pos)); } else { 교환(pos, rightChild(pos)); maxHeapify(rightChild(pos)); } } } // 방법 7 // 최대 힙에 새 요소를 삽입합니다. public void insert(int element) { Heap[size] = element; // 위반된 속성을 위로 탐색하고 수정합니다. int current = size; while (힙[현재]> 힙[부모(현재)]) { swap(현재, 부모(현재)); 현재 = 부모(현재); } 크기++; } // 방법 8 // 힙을 표시하려면 public void print() { for (int i = 0; i 2; i++) { System.out.print('Parent Node : ' + Heap[i]); if (leftChild(i) // 자식이 // 배열의 경계를 벗어난 경우 System.out.print(' 왼쪽 자식 노드: ' + Heap[leftChild(i)]); if (rightChild(i ) // 오른쪽 자식 인덱스는 // 배열의 인덱스를 벗어나면 안 됩니다. System.out.print(' 오른쪽 자식 노드: ' + Heap[rightChild(i)]) System.out.println() ; // 새 줄 } } // 방법 9 // 최대 힙에서 요소 제거 public int extractMax() { int popped = Heap[0] = Heap[--size]; ; return popped; } // 메서드 10 // 기본 드라이버 메서드 public static void main(String[] arg) { // 더 나은 가독성을 위해 메시지 표시 System.out.println('The Max Heap is '); = new MaxHeap(15); // 노드 삽입 // 사용자 정의 입력 maxHeap.insert(3); maxHeap.insert(10); maxHeap.insert(19); maxHeap.insert(22); maxHeap.insert(9); // 위에 정의된 대로 maxHeap() 호출 maxHeap.print(); 힙의 값 System.out.println('최대값은 ' + maxHeap.extractMax()); } }> |
>
문자열.java의 값
자바스크립트 수면
>산출
The Max Heap is Parent Node : 84 Left Child Node: 22 Right Child Node: 19 Parent Node : 22 Left Child Node: 17 Right Child Node: 10 Parent Node : 19 Left Child Node: 5 Right Child Node: 6 Parent Node : 17 Left Child Node: 3 Right Child Node: 9 The max val is 84>
방법 2: 라이브러리를 통해 Collections.reverseOrder() 메서드 사용
Java에서 Heap을 구현하기 위해 PriorityQueue 클래스를 사용합니다. 기본적으로 최소 힙은 이 클래스에 의해 구현됩니다. Max Heap을 구현하기 위해 Collections.reverseOrder() 메소드를 사용합니다.
예
자바
// Java program to demonstrate working> // of PriorityQueue as a Max Heap> // Using Collections.reverseOrder() method> // Importing all utility classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue> >=>new> PriorityQueue(> >Collections.reverseOrder());> >// Adding items to our priority queue> >// using add() method> >pQueue.add(>10>);> >pQueue.add(>30>);> >pQueue.add(>20>);> >pQueue.add(>400>);> >// Printing the most priority element> >System.out.println(>'Head value using peek function:'> >+ pQueue.peek());> >// Printing all elements> >System.out.println(>'The queue elements:'>);> >Iterator itr = pQueue.iterator();> >while> (itr.hasNext())> >System.out.println(itr.next());> >// Removing the top priority element (or head) and> >// printing the modified pQueue using poll()> >pQueue.poll();> >System.out.println(>'After removing an element '> >+>'with poll function:'>);> >Iterator itr2 = pQueue.iterator();> >while> (itr2.hasNext())> >System.out.println(itr2.next());> >// Removing 30 using remove() method> >pQueue.remove(>30>);> >System.out.println(>'after removing 30 with'> >+>' remove function:'>);> >Iterator itr3 = pQueue.iterator();> >while> (itr3.hasNext())> >System.out.println(itr3.next());> >// Check if an element is present using contains()> >boolean> b = pQueue.contains(>20>);> >System.out.println(>'Priority queue contains 20 '> >+>'or not?: '> + b);> >// Getting objects from the queue using toArray()> >// in an array and print the array> >Object[] arr = pQueue.toArray();> >System.out.println(>'Value in array: '>);> >for> (>int> i =>0>; i System.out.println('Value: ' + arr[i].toString()); } }> |
>
평균 대 평균
>산출
Head value using peek function:400 The queue elements: 400 30 20 10 After removing an element with poll function: 30 10 20 after removing 30 with remove function: 20 10 Priority queue contains 20 or not?: true Value in array: Value: 20 Value: 10>