힙 데이터 구조: 힙이란 무엇입니까? 최소 및 최대 힙(예)
힙이란 무엇입니까?
힙은 특수 트리 데이터 구조입니다. 힙은 루트(부모)라고 하는 최상위 노드로 구성됩니다. 두 번째 자식은 루트의 왼쪽 자식이고, 세 번째 노드는 루트의 오른쪽 자식입니다. 연속적인 노드는 왼쪽에서 오른쪽으로 채워집니다. 부모 노드 키는 자식의 키와 비교되고 적절한 배열이 발생합니다. 트리는 각 엔터티를 노드라고 하는 곳에서 시각화하기 쉽습니다. 노드에는 식별을 위한 고유한 키가 있습니다.
힙 데이터 구조가 필요한 이유는 무엇입니까?
힙 데이터 구조를 사용하는 주요 이유는 다음과 같습니다.
- 힙 데이터 구조는 로그 시간(O(log)으로 삭제 및 삽입을 허용합니다.2엔).
- 트리의 데이터는 특정 순서로 구성됩니다. 프로그래머는 최대값이나 최소값 등을 업데이트하거나 쿼리하는 것 외에도 부모와 자식 간의 관계를 찾을 수 있습니다.
- 의 개념을 적용할 수 있습니다. 문서 객체 모델 힙 데이터 구조를 이해하는 데 도움이 됩니다.
힙의 유형
힙 데이터 구조에는 우선순위 큐, 이진 힙, 이항 힙을 포함하여 힙 데이터 구조에서 삽입을 처리하고 요소를 제거하기 위한 다양한 알고리즘이 있습니다. 힙 정렬.
- 우선순위 대기열: 우선순위가 지정된 객체를 포함하는 추상 데이터 구조입니다. 각 개체나 항목에는 미리 정해진 우선순위가 있습니다. 따라서 더 높은 우선순위가 할당된 객체나 항목이 나머지보다 먼저 서비스를 받습니다.
- 바이너리 힙: 이진 힙은 삭제, 삽입과 같은 간단한 힙 연산에 적합합니다.
- 이항 힙: 이항 힙은 힙을 구성하는 일련의 이항 트리 컬렉션으로 구성됩니다. 이항 힙 트리는 엄격하게 정의되어 있으므로 일반적인 트리가 아닙니다. 이항 트리의 총 요소 수는 항상 2를 갖습니다.n 노드.
- 힙 정렬: 대부분의 정렬 알고리즘과 달리 힙 정렬은 정렬 작업에 O(1) 공간을 사용합니다. 이것은 먼저 최대 힙으로 전환하여 증가하는 순서로 정렬이 발생하는 비교 기반 정렬 알고리즘입니다. 힙 정렬을 업그레이드된 품질의 이진 검색 트리로 볼 수 있습니다.
일반적으로 힙 데이터 구조는 두 가지 전략을 사용합니다. 입력 12 – 8 – 4 – 2 및 1의 경우
- 최소 힙 – 맨 위에 있는 최소 값
- 최대 힙 – 맨 위의 가장 높은 값
최소 힙
최소 힙 구조에서 루트 노드는 해당 노드의 하위 노드보다 작거나 같은 값을 갖습니다. 최소 힙의 이 힙 노드는 최소값을 보유합니다. 전체적으로, 최소 힙 구조는 완전합니다. 이진 트리.
트리에 최소 힙이 있으면 모든 잎이 실행 가능한 후보가 됩니다. 그러나 정확한 Max-heap 값을 얻으려면 각 리프를 검사해야 합니다.
최소 힙 예
위의 다이어그램에서는 루트에서 가장 낮은 노드까지 명확한 순서를 볼 수 있습니다.
Array Array_N[12,2,8,1,4]에 요소를 저장한다고 가정합니다. 배열에서 볼 수 있듯이 루트 요소는 Min Heap 우선순위를 위반하고 있습니다. Min Heap 속성을 유지하려면 Min-Heapify 연산을 수행하여 Min Heap 속성이 충족될 때까지 요소를 바꿔야 합니다.
최대 힙
Max Heap의 구조에서 상위 또는 루트 노드는 노드의 하위 노드와 같거나 더 큰 값을 갖습니다. 이 노드는 최대값을 보유합니다. 게다가 이는 완전한 이진 트리이므로 값 모음에서 최대 힙을 구축하고 O(n) 시간에 실행할 수 있습니다.
다음은 Java Max 힙을 구현하는 몇 가지 방법입니다.
- 추가하다 (): 새 요소를 힙에 배치합니다. 배열을 사용하는 경우 개체는 배열의 끝에 추가되는 반면, 이진 트리에서는 개체가 위에서 아래로 추가된 다음 왼쪽에서 오른쪽으로 추가됩니다.
- 제거하다 (): 이 방법을 사용하면 배열 목록에서 첫 번째 요소를 제거할 수 있습니다. 새로 추가된 요소는 더 이상 가장 큰 요소가 아니므로 Sift-Down 메서드는 항상 해당 요소를 새 위치로 푸시합니다.
- 선별(): 이 방법은 루트 객체를 자식 객체와 비교한 다음 새로 추가된 노드를 올바른 위치에 밀어넣습니다.
- 선별 (): 배열 방법을 사용하여 새로 삽입된 요소를 배열에 추가하는 경우 Sift-Up 방법은 새로 추가된 노드가 새 위치로 재배치되도록 돕습니다. 새로 삽입된 항목은 먼저 트리 데이터 구조를 시뮬레이션하여 상위 항목과 비교됩니다.
Parent_Index=Child_Index/2 공식을 적용합니다. 최대 요소가 배열 앞에 올 때까지 이 작업을 계속합니다.
기본 힙 OperaTIONS
데이터 집합에서 가장 높은 값과 가장 낮은 값을 찾으려면 find, delete, insert와 같은 많은 기본 힙 작업이 필요합니다. 요소는 끊임없이 오고 가기 때문에 다음을 수행해야 합니다.
- Find – 더미에서 항목을 찾으십시오.
- 끼워 넣다 – 새로운 하위 항목을 힙에 추가합니다.
- . – 힙에서 노드를 삭제합니다.
힙 생성
힙을 구성하는 과정은 힙 생성이라고 합니다. 키 목록이 주어지면 프로그래머는 빈 힙을 만든 다음 기본 힙 연산을 사용하여 한 번에 하나씩 다른 키를 삽입합니다.
이제 Willaim의 방법을 사용하여 힙에 값 12,2,8,1 및 4를 삽입하여 최소 힙을 구축해 보겠습니다. 빈 힙으로 시작한 다음 O(nlogn) 시간을 사용하여 다른 요소로 연속적으로 채워 n 요소로 힙을 구축할 수 있습니다.
- Heapify: 삽입 알고리즘에서 요소를 힙에 삽입하는 데 도움이 됩니다. 강조된 속성 힙 데이터 구조가 따르는지 확인합니다.
예를 들어, max heapify는 부모의 값이 자식보다 큰지 확인합니다. 그런 다음 요소를 스와핑과 같은 방법을 사용하여 정렬할 수 있습니다.
- 병합: 하나로 결합할 두 개의 힙이 있다는 점을 고려하면 병합 힙을 사용하여 두 힙의 값을 함께 가져옵니다. 그러나 원래 힙은 여전히 보존됩니다.
힙 검사
힙 검사는 힙 데이터 구조의 요소 수를 확인하고 힙이 비어 있는지 확인하는 것을 의미합니다.
힙을 요소의 정렬 또는 큐잉으로 검사하는 것이 중요합니다. Is-Empty()를 사용하여 처리할 요소가 있는지 확인하는 것이 중요합니다. 힙 크기는 최대 힙 또는 최소 힙을 찾는 데 도움이 됩니다. 따라서 힙 속성 다음에 나오는 요소를 알아야 합니다.
- 크기 – 힙의 크기 또는 길이를 반환합니다. 정렬된 순서로 몇 개의 요소가 있는지 알 수 있습니다.
- 비었다 – 힙이 NULL이면 TRUE를 반환하고, 그렇지 않으면 FALSE를 반환합니다.
여기에서는 우선순위Q 루프를 실행한 다음 우선순위Q가 비어 있지 않은지 확인합니다.
//print head the head values While (!priorityQ.isEmpty()) { System.out.print(priorityQ.poll()+" ");
힙 데이터 구조의 사용
힙 데이터 구조는 다음과 같은 실제 생활의 많은 프로그래밍 애플리케이션에 유용합니다.
- 스팸 필터링에 도움이 됩니다.
- 그래프 알고리즘 구현.
- Opera시스템 로드 밸런싱 및 데이터 압축.
- 통계에서 순서를 찾아보세요.
- 로그 시간에 목록의 항목을 검색할 수 있는 우선순위 대기열을 구현합니다.
- 힙 데이터 구조는 정렬에도 사용됩니다.
- 라인에 있는 고객을 시뮬레이션합니다.
- 인터럽트 처리 Opera팅 시스템.
- Huffman의 데이터 압축 코딩에서.
힙 우선순위 대기열 속성
- 우선순위 힙에서는 목록의 데이터 항목을 서로 비교하여 더 작은 요소를 결정합니다.
- 요소는 대기열에 배치된 후 제거됩니다.
- 우선순위 큐의 모든 단일 요소에는 우선순위로 식별되는 고유 번호가 있습니다.
- 우선순위 큐를 종료하면 우선순위가 가장 높은 요소가 먼저 종료됩니다.
힙 우선순위 큐를 구현하는 단계 Java
코드 예제를 사용한 JAVA의 힙 정렬
import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = {5, 9, 3, 1, 8, 6}; // Sort the array using heap sort heapSort(arr); // Print the sorted array System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { // Convert the array into a heap for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, arr.length, i); } // Extract the maximum element from the heap and place it at the end of the array for (int i = arr.length - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // Find the largest element among the root, left child, and right child if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } }
산출
Original Array: 5 9 3 1 8 6 Heap after insertion: 9 8 6 1 5 3 Heap after sorting: 1 3 5 6 8 9
힙 정렬 Python 코드 예시 포함
def heap_sort(arr): """ Sorts an array in ascending order using heap sort algorithm. Parameters: arr (list): The array to be sorted. Returns: list: The sorted array. """ n = len(arr) # Build a max heap from the array for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements from the heap one by one for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] # swap the root with the last element heapify(arr, i, 0) # heapify the reduced heap return arr def heapify(arr, n, i): """ Heapifies a subtree with the root at index i in the given array. Parameters: arr (list): The array containing the subtree to be heapified. n (int): The size of the subtree. i (int): The root index of the subtree. """ largest = i # initialize largest as the root left = 2 * i + 1 # left child index right = 2 * i + 2 # right child index # If left child is larger than root if left < n and arr[left] > arr[largest]: largest = left # If right child is larger than largest so far if right < n and arr[right] > arr[largest]: largest = right # If largest is not root if largest != i: arr[i], arr[largest] = ( arr[largest], arr[i], ) # swap the root with the largest element heapify(arr, n, largest) # recursively heapify the affected subtree arr = [4, 1, 3, 9, 7] sorted_arr = heap_sort(arr) print(sorted_arr)
산출
[1, 3, 4, 7, 9]
다음으로 알아볼 내용은 이분법
요약
- 힙은 특수한 트리 데이터 구조입니다. 부모와 자녀가 있는 가계도를 상상해 봅시다.
- 힙 데이터 구조 Java 로그 시간에 삭제 및 삽입 허용 – O(log2엔).
- 힙 Python 우선순위 큐, 이진 힙, 이항 힙, 힙 정렬을 포함하여 힙 데이터 구조에서 삽입을 처리하고 요소를 제거하기 위한 다양한 알고리즘을 갖고 있습니다.
- 최소 힙 구조에서 루트 노드는 해당 노드의 하위 노드보다 작거나 같은 값을 갖습니다.
- Max Heap의 구조에서 루트 노드(상위)는 노드의 하위 노드와 같거나 큰 값을 갖습니다.
- 힙 검사는 힙 데이터 구조의 요소 수를 확인하고 힙이 비어 있는지 확인하는 것을 의미합니다.