what is heap data structure java
이 자습서에서는 Java 힙 데이터 구조 및 Min Heap, Max Heap, Heap Sort, Stack vs Heap과 같은 관련 개념에 대해 설명합니다.
힙은 Java의 특수 데이터 구조입니다. 힙은 트리 기반 데이터 구조이며 완전한 이진 트리로 분류 될 수 있습니다. 힙의 모든 노드는 특정 순서로 정렬됩니다.
=> 모두를위한 Java 교육 시리즈를 보려면 여기를 방문하십시오.
학습 내용 :
자바의 힙 데이터 구조
힙 데이터 구조에서 루트 노드는 하위 노드와 비교되고 순서에 따라 정렬됩니다. 따라서 a가 루트 노드이고 b가 자식이면 속성, 키 (a)> = 키 (b) 최대 힙을 생성합니다.
위의 루트와 자식 노드의 관계를“Heap Property”라고합니다.
부모-자식 노드의 순서에 따라 힙은 일반적으로 두 가지 유형이 있습니다.
# 1) 최대 힙 :Max-Heap에서 루트 노드 키는 힙에있는 모든 키 중 가장 큰 키입니다. 힙의 모든 하위 트리에 대해 동일한 속성이 재귀 적으로 참인지 확인해야합니다.
아래 다이어그램은 샘플 최대 힙을 보여줍니다. 루트 노드는 하위 노드보다 큽니다.
# 2) Min-Heap :Min-Heap의 경우 루트 노드 키는 힙에있는 다른 모든 키 중에서 가장 작거나 최소입니다. Max 힙에서와 같이이 속성은 힙의 다른 모든 하위 트리에서 재귀 적으로 true 여야합니다.
예, Min-heap 트리의 아래에 나와 있습니다. 보시다시피 루트 키는 힙에있는 다른 모든 키 중 가장 작습니다.
힙 데이터 구조는 다음 영역에서 사용할 수 있습니다.
- 힙은 주로 우선 순위 대기열을 구현하는 데 사용됩니다.
- 특히 min-heap은 Graph에서 정점 사이의 최단 경로를 결정하는 데 사용할 수 있습니다.
이미 언급했듯이 힙 데이터 구조는 루트 및 하위에 대한 힙 속성을 충족하는 완전한 이진 트리입니다. 이 힙은 바이너리 힙 .
바이너리 힙
바이너리 힙은 다음 속성을 충족합니다.
- 바이너리 힙은 완전한 바이너리 트리입니다. 완전한 이진 트리에서 마지막 레벨을 제외한 모든 레벨이 완전히 채워집니다. 마지막 수준에서 키는 가능한 한 왼쪽에 있습니다.
- 힙 속성을 충족합니다. 바이너리 힙은 만족하는 힙 속성에 따라 최대 또는 최소 힙이 될 수 있습니다.
바이너리 힙은 일반적으로 배열로 표시됩니다. 완전한 이진 트리이므로 배열로 쉽게 표현할 수 있습니다. 따라서 이진 힙의 배열 표현에서 루트 요소는 A (0)이됩니다. 여기서 A는 이진 힙을 나타내는 데 사용되는 배열입니다.
그래서 일반적으로 나는일이진 힙 배열 표현 A (i)에서 노드를 사용하면 아래와 같이 다른 노드의 인덱스를 나타낼 수 있습니다.
| A ((i-1) / 2) | 부모 노드를 나타냅니다. |
|---|---|
| 액세스가 더 빠릅니다. | 스택보다 느립니다. |
| A ((2 * i) +1) | 왼쪽 자식 노드를 나타냅니다. |
| A ((2 * i) +2) | 오른쪽 자식 노드를 나타냅니다. |
다음 바이너리 힙을 고려하십시오.
위 최소 바이너리 힙의 배열 표현은 다음과 같습니다.
위에 표시된대로 힙은 레벨 순서 즉, 요소는 각 레벨에서 왼쪽에서 오른쪽으로 이동합니다. 한 수준의 요소가 고갈되면 다음 수준으로 이동합니다.
다음으로 Java로 바이너리 힙을 구현합니다.
아래 프로그램은 Java의 바이너리 힙을 보여줍니다.
import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap(i); while(i>0 && temp > heap(parent(i))){ heap(i) = heap(parent(i)); i = parent(i); } heap(i) = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i 산출:
nHeap = 7 4 6 1 3 2 5
Java의 최소 힙
Java의 최소 힙은 완전한 이진 트리입니다. 최소 힙에서 루트 노드는 힙의 다른 모든 노드보다 작습니다. 일반적으로 각 내부 노드의 키 값은 하위 노드보다 작거나 같습니다.
최소 힙의 배열 표현과 관련하여 노드가 'i'위치에 저장되면 왼쪽 자식 노드가 위치 2i + 1에 저장되고 오른쪽 자식 노드가 위치 2i + 2에 저장됩니다. 위치 (i-1) / 2는 부모 노드를 반환합니다.
다음은 min-heap에서 지원하는 다양한 작업입니다.
# 1) 삽입 () : 처음에는 새 키가 트리 끝에 추가됩니다. 키가 부모 노드보다 크면 힙 속성이 유지됩니다. 그렇지 않으면 힙 속성을 충족하기 위해 키를 위쪽으로 이동해야합니다. 최소 힙의 삽입 작업은 O (log n) 시간이 걸립니다.
# 2) extractMin () : 이 작업은 힙에서 최소 요소를 제거합니다. 힙에서 루트 요소 (최소 요소)를 제거한 후 힙 속성을 유지해야합니다. 이 전체 작업에는 O (로그온)가 필요합니다.
# 3) getMin () : getMin ()은 최소 요소이기도 한 힙의 루트를 반환합니다. 이 작업은 O (1) 시간에 수행됩니다.
다음은 Min-heap에 대한 예제 트리입니다.
위의 다이어그램은 최소 힙 트리를 보여줍니다. 우리는 트리의 루트가 트리의 최소 요소임을 알 수 있습니다. 루트가 위치 0에 있으므로 왼쪽 자식은 2 * 0 + 1 = 1에, 오른쪽 자식은 2 * 0 + 2 = 2에 있습니다.
최소 힙 알고리즘
다음은 최소 힙을 구축하는 알고리즘입니다.
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }Java에서 최소 힙 구현
배열 또는 우선 순위 대기열을 사용하여 최소 힙을 구현할 수 있습니다. 우선 순위 큐가 최소 힙으로 구현되므로 우선 순위 큐를 사용하여 최소 힙을 구현하는 것이 기본 구현입니다.
다음 Java 프로그램은 Arrays를 사용하여 최소 힙을 구현합니다. 여기서는 힙에 대한 배열 표현을 사용하고 힙에 추가 된 각 요소의 힙 속성을 유지하기 위해 heapify 함수를 적용합니다. 마지막으로 힙을 표시합니다.
class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } } 산출:
자바의 최대 힙
최대 힙은 완전한 이진 트리이기도합니다. 최대 힙에서 루트 노드는 하위 노드보다 크거나 같습니다. 일반적으로 최대 힙에있는 내부 노드의 값은 하위 노드보다 크거나 같습니다.
최대 힙이 배열에 매핑되는 동안 노드가 'i'위치에 저장되면 왼쪽 자식은 2i +1에 저장되고 오른쪽 자식은 2i + 2에 저장됩니다.
일반적인 최대 힙은 다음과 같이 표시됩니다.
위의 다이어그램에서 루트 노드는 힙에서 가장 크고 하위 노드의 값은 루트 노드보다 작습니다.
min-heap과 유사하게 max heap도 배열로 표시 될 수 있습니다.
따라서 A가 최대 힙을 나타내는 배열이면 A (0)이 루트 노드입니다. 마찬가지로, A (i)가 최대 힙의 노드 인 경우 다음은 배열을 사용하여 표현할 수있는 다른 인접 노드입니다.
- ((i-1) / 2)는 A (i)의 부모 노드를 나타냅니다.
- ((2i +1))은 A (i)의 왼쪽 자식 노드를 나타냅니다.
- A (2i + 2)는 A (i)의 오른쪽 자식 노드를 반환합니다.
Max Heap에서 수행 할 수있는 작업은 다음과 같습니다.
# 1) 삽입 : 삽입 작업은 최대 힙 트리에 새 값을 삽입합니다. 트리 끝에 삽입됩니다. 새 키 (값)가 부모 노드보다 작 으면 힙 속성이 유지됩니다. 그렇지 않으면 힙 속성을 유지하기 위해 트리를 힙화해야합니다.
웹 서비스를 어떻게 테스트합니까
삽입 작업의 시간 복잡도는 O (log n)입니다.
# 2) ExtractMax : ExtractMax 작업은 최대 힙에서 최대 요소 (root)를 제거합니다. 이 작업은 힙 속성을 유지하기 위해 최대 힙도 힙화합니다. 이 작업의 시간 복잡도는 O (log n)입니다.
# 3) getMax : getMax 작업은 시간 복잡도가 O (1) 인 최대 힙의 루트 노드를 반환합니다.
아래 Java 프로그램은 최대 힙을 구현합니다. 여기서 ArrayList를 사용하여 최대 힙 요소를 나타냅니다.
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } } 산출:
Java의 우선 순위 대기열 최소 힙
Java의 우선 순위 큐 데이터 구조는 최소 힙을 나타내는 데 직접 사용할 수 있습니다. 기본적으로 우선 순위 큐는 최소 힙을 구현합니다.
아래 프로그램은 Priority Queue를 사용하여 Java의 최소 힙을 보여줍니다.
import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } 산출:
Java의 우선 순위 대기열 최대 힙
Priority 큐를 사용하여 Java에서 최대 힙을 나타내려면 Collections.reverseOrder를 사용하여 최소 힙을 반전해야합니다. 우선 순위 큐는 Java에서 최소 힙을 직접 나타냅니다.
아래 프로그램에서 Priority 큐를 사용하여 Max Heap을 구현했습니다.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } 산출:
자바의 힙 정렬
힙 정렬은 각 반복에 대해 배열에서 최대 요소를 선택하는 선택 정렬과 유사한 비교 정렬 기술입니다. 힙 정렬은 힙 데이터 구조를 사용하고 정렬 할 배열 요소에서 최소 또는 최대 힙을 만들어 요소를 정렬합니다.
이미 최소 및 최대 힙에서 루트 노드에는 배열의 최소 및 최대 요소가 포함된다는 점에 대해 이미 논의했습니다. 힙 정렬에서는 힙의 루트 요소 (최소 또는 최대)가 제거되고 정렬 된 배열로 이동됩니다. 나머지 힙은 힙 속성을 유지하기 위해 힙화됩니다.
따라서 힙 정렬을 사용하여 주어진 배열을 정렬하려면 두 단계를 재귀 적으로 수행해야합니다.
- 주어진 배열에서 힙을 빌드하십시오.
- 힙에서 루트 요소를 반복적으로 제거하고 정렬 된 배열로 이동하십시오. 나머지 힙을 힙화하십시오.
힙 정렬의 시간 복잡성은 모든 경우에 O (n log n)입니다. 공간 복잡도는 O (1)입니다.
자바의 힙 정렬 알고리즘
다음은 지정된 배열을 오름차순 및 내림차순으로 정렬하는 힙 정렬 알고리즘입니다.
# 1) 오름차순으로 정렬하는 힙 정렬 알고리즘 :
- 정렬 할 지정된 배열의 최대 힙을 만듭니다.
- 루트 (입력 배열의 최대 값)를 삭제하고 정렬 된 배열로 이동합니다. 배열의 마지막 요소를 루트에 놓습니다.
- 힙의 새 루트를 힙화하십시오.
- 전체 배열이 정렬 될 때까지 1 단계와 2 단계를 반복합니다.
# 2) 내림차순으로 정렬하는 힙 정렬 알고리즘 :
- 주어진 배열에 대한 최소 힙을 생성합니다.
- 루트 (배열의 최소값)를 제거하고 배열의 마지막 요소로 바꿉니다.
- 힙의 새 루트를 힙화하십시오.
- 전체 배열이 정렬 될 때까지 1 단계와 2 단계를 반복합니다.
자바에서 힙 정렬 구현
아래 Java 프로그램은 힙 정렬을 사용하여 오름차순으로 배열을 정렬합니다. 이를 위해 먼저 최대 힙을 구성한 다음 위의 알고리즘에 지정된대로 루트 요소를 재귀 적으로 스왑하고 힙화합니다.
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } } 산출:
힙 정렬 기술의 전체 시간 복잡도는 O (nlogn)입니다. heapify 기술의 시간 복잡성은 O (로그온)입니다. 힙 빌드의 시간 복잡도는 O (n)입니다.
자바에서 스택 대 힙
이제 스택 데이터 구조와 힙 간의 몇 가지 차이점을 표로 만들어 보겠습니다.
스택 더미 스택은 선형 데이터 구조입니다. 힙은 계층 적 데이터 구조입니다. LIFO (Last In, First Out) 주문을 따릅니다. 순회는 레벨 순서입니다. 주로 정적 메모리 할당에 사용됩니다. 동적 메모리 할당에 사용됩니다. 메모리는 연속적으로 할당됩니다. 메모리는 임의의 위치에 할당됩니다. 스택 크기는 운영 체제에 따라 제한됩니다. 운영 체제에서 적용하는 힙 크기에는 제한이 없습니다. 스택은 지역 변수에만 액세스 할 수 있습니다. 힙에는 할당 된 전역 변수가 있습니다. 메모리 할당 / 할당 해제는 자동입니다. 할당 / 할당 해제는 프로그래머가 수동으로 수행해야합니다. 스택은 Arrays, Linked List, ArrayList 등 또는 기타 선형 데이터 구조를 사용하여 구현할 수 있습니다. 힙은 배열 또는 트리를 사용하여 구현됩니다. 적은 경우 유지 관리 비용. 유지 비용이 더 많이 듭니다. 메모리가 제한되어있어 메모리 부족이 발생할 수 있습니다. 메모리 부족은 없지만 메모리 조각화가 발생할 수 있습니다.
자주 묻는 질문
Q # 1) 스택이 힙보다 빠르나요?
대답: 액세스는 힙에 비해 스택에서 선형이므로 스택은 힙보다 빠릅니다.
Q # 2) 힙의 용도는 무엇입니까?
대답: 힙은 주로 Dijkstra의 알고리즘과 같은 두 지점 사이의 최소 또는 최단 경로를 찾는 알고리즘, 힙 정렬을 사용하여 정렬, 우선 순위 큐 구현 (최소 힙) 등에 사용됩니다.
Q # 3) 힙이란 무엇입니까? 그 유형은 무엇입니까?
대답: 힙은 계층 적 트리 기반 데이터 구조입니다. 힙은 완전한 이진 트리입니다. 힙은 두 가지 유형, 즉 루트 노드가 모든 노드 중에서 가장 큰 최대 힙입니다. 루트 노드가 모든 키 중에서 가장 작거나 최소 인 최소 힙입니다.
Q # 4) 스택에 비해 힙의 장점은 무엇입니까?
대답: 스택에 대한 힙의 주요 장점은 힙에 있으며 메모리는 동적으로 할당되므로 사용할 수있는 메모리 양에 제한이 없습니다. 둘째, 스택에는 로컬 변수 만 할당 할 수 있으며 힙에는 전역 변수를 할당 할 수도 있습니다.
Q # 5) 힙이 중복 될 수 있습니까?
대답: 예, 힙은 완전한 이진 트리이고 이진 검색 트리의 속성을 충족하지 않기 때문에 힙에 중복 키가있는 노드를 갖는 데 제한이 없습니다.
결론
이 자습서에서는 힙 유형을 사용하여 힙 유형 및 힙 정렬에 대해 설명했습니다. 또한 Java에서 해당 유형의 세부 구현을 보았습니다.
=> 여기에서 완벽한 Java 교육 가이드를 확인하십시오.
추천 도서
