힙 데이터 구조: 힙이란 무엇인가?

힙 데이터 구조란 무엇인가요?

힙은 특수한 트리 기반 데이터 구조입니다. 힙 데이터 구조는 최상위 노드인 루트(부모)로 구성됩니다. 두 번째 노드는 루트의 왼쪽 자식이고, 세 번째 노드는 루트의 오른쪽 자식입니다. 이후 노드들은 왼쪽에서 오른쪽으로 채워집니다. 부모 노드의 키는 자식 노드의 키와 비교되어 올바른 순서로 정렬됩니다. 각 개체를 노드라고 하고, 각 노드는 고유한 식별 키를 가지고 있어 트리 구조를 쉽게 시각화할 수 있습니다.

간단히 말해, 힙은 힙 속성을 만족하는 완전 이진 트리입니다. 즉, 모든 부모 노드가 자식 노드에 대해 일관된 순서를 가지므로 우선순위 큐와 힙 정렬에 이상적입니다.

힙 데이터 구조가 필요한 이유는 무엇입니까?

힙을 사용하는 주요 이유는 다음과 같습니다.

• 힙 데이터 구조는 로그 시간(O(log)) 내에 삭제 및 삽입을 허용합니다.₂엔).
• 트리 구조의 데이터는 특정 순서로 배열되어 있습니다. 프로그래머는 최대값이나 최소값과 같은 값을 업데이트하거나 조회하는 것 외에도 부모 노드와 자식 노드 간의 관계를 파악할 수 있습니다.
• 의 개념을 적용할 수 있습니다. 문서 객체 모델 힙 데이터 구조를 시각적으로 이해하는 데 도움이 됩니다.
• 힙은 효율적인 우선순위 큐 연산을 지원하며, 이는 다익스트라 최단 경로 알고리즘이나 프림 최소 신장 트리 알고리즘과 같은 그래프 알고리즘에 매우 중요합니다.

힙의 유형

힙 데이터 구조는 우선순위 큐, 이진 힙, 이항 힙 등 요소 삽입 및 제거를 처리하는 다양한 알고리즘을 제공합니다. 힙 정렬.

• 우선순위 대기열: 복근입니다trac우선순위가 지정된 객체를 포함하는 데이터 구조입니다. 각 객체 또는 항목에는 미리 정해진 우선순위가 있습니다. 따라서 우선순위가 높은 객체 또는 항목이 다른 객체 또는 항목보다 먼저 서비스를 받습니다.
• 바이너리 힙: 바이너리 힙은 삭제 및 삽입과 같은 간단한 힙 연산에 적합합니다. 대부분의 표준 라이브러리 우선순위 큐에서 기본적으로 사용되는 구현 방식입니다.
• 이항 힙: 이항 힙은 힙을 구성하는 이항 트리들의 모음으로 이루어져 있습니다. 이항 힙 트리는 엄밀하게 정의되어 있기 때문에 일반적인 트리와는 다릅니다. 이항 트리의 전체 요소 개수는 항상 2¹⁰개입니다.ⁿ 노드.
• 힙 정렬: 대부분의 정렬 알고리즘과 달리 힙 정렬은 정렬 연산에 O(1) 공간을 사용합니다. 이는 비교 기반 정렬 알고리즘으로, 입력을 최대 힙으로 변환한 후 오름차순으로 정렬합니다. 힙 정렬은 업그레이드된 이진 탐색 트리로 볼 수 있습니다.

일반적으로 힙 데이터 구조는 두 가지 전략을 사용합니다. 입력 12 – 8 – 4 – 2 및 1의 경우:

• 최소 힙 - 최상단에 가장 낮은 값이 위치함
• 최대 힙 – 가장 높은 값이 맨 위에 있습니다

최소 힙

최소힙 구조에서 루트 노드는 자식 노드들의 값과 같거나 그보다 작은 값을 가집니다. 따라서 최소힙의 루트는 최솟값을 지닙니다. 또한 최소힙은 완전 이진 트리입니다.

트리에 최소힙(Min-Heap)이 형성되면 모든 리프 노드가 최댓값 후보가 됩니다. 하지만 정확한 최대힙(Max-Heap) 값을 얻으려면 각 리프 노드를 하나씩 검사해야 합니다.

최소힙 예제

위 그림에서 루트에서 최하위 노드까지 명확한 순서가 나타나는 것을 확인할 수 있습니다.

배열 Array_N[12, 2, 8, 1, 4]에 요소들이 저장되어 있다고 가정해 봅시다. 배열을 보면 루트 요소가 최소힙 우선순위를 위반하고 있음을 알 수 있습니다. 최소힙 속성을 유지하려면 최소힙 규칙이 충족될 때까지 요소들을 교환하는 최소힙화 연산을 수행해야 합니다.

최대 힙

최대힙 구조에서 부모 또는 루트 노드는 자식 노드보다 크거나 같은 값을 가집니다. 이 노드는 최댓값을 저장합니다. 최대힙은 완전 이진 트리이므로 값들의 모음으로부터 O(n) 시간 안에 최대힙을 구축할 수 있습니다.

다음은 구현 시 일반적으로 사용되는 몇 가지 방법입니다. Java 최대 힙:

• 추가하다 (): 힙에 새 요소를 추가합니다. 배열을 사용하는 경우 객체는 배열의 끝에 추가되는 반면, 이진 트리에서는 객체가 위에서 아래로, 그 다음 왼쪽에서 오른쪽으로 추가됩니다.
• 제거하다 (): 이 메서드를 사용하면 배열 리스트에서 첫 번째 요소를 제거할 수 있습니다. 새로 상위 요소로 승격된 요소는 더 이상 가장 큰 요소가 아니므로, Sift-Down 메서드는 항상 해당 요소를 새로운 위치로 이동시킵니다.
• 체질하기 (): 이 메서드는 루트 객체를 자식 객체와 비교한 다음, 재배치된 노드를 올바른 위치로 이동시킵니다.
• 체질하기(): 배열 메서드를 사용하여 배열에 새 요소를 삽입하는 경우, Sift-Up 메서드는 새로 추가된 노드가 올바른 위치로 이동하도록 도와줍니다. 새 항목은 먼저 트리 데이터 구조를 모방하여 부모 항목과 비교됩니다.

  Parent_Index = Child_Index / 2 공식을 적용합니다. 배열에서 가장 큰 요소가 맨 앞에 올 때까지 이 과정을 반복합니다.

기본 힙 OperaTIONS

데이터 집합에서 최고값과 최저값을 찾으려면 찾기, 삽입, 삭제와 같은 몇 가지 기본적인 힙 연산이 필요합니다. 요소들이 끊임없이 추가되고 삭제되기 때문에 다음과 같은 방법을 알아야 합니다.

• Find – 더미에서 항목을 찾으십시오.
• 끼워 넣다 – 새로운 하위 항목을 힙에 추가합니다.
• . – 힙에서 노드를 삭제합니다.

힙 생성

힙을 구성하는 과정을 힙 생성이라고 합니다. 프로그래머는 키 목록이 주어지면 빈 힙을 만들고 기본적인 힙 연산을 사용하여 나머지 키들을 하나씩 삽입합니다.

이제 윌리엄의 방법을 사용하여 12, 2, 8, 1, 4 값을 삽입하여 최소 힙을 구축해 보겠습니다. n개의 요소를 가진 힙은 빈 힙에서 시작하여 순차적으로 요소를 채워나가는 방식으로 O(n log n) 시간 안에 구축할 수 있습니다.

• 힙파이: 힙 속성을 유지하면서 힙에 요소를 삽입하는 데 도움이 되는 삽입 루틴입니다.

  예를 들어, 최대 힙화(max-heapify) 연산은 부모 요소의 값이 자식 요소의 값보다 큰지 확인합니다. 그런 다음 스왑(swap)과 같은 메서드를 사용하여 요소를 정렬할 수 있습니다.ping.

• 병합 : 두 개의 힙을 하나로 합칠 때는 병합 연산을 사용하여 두 힙의 값을 결합합니다. 원래 힙은 그대로 유지됩니다.

힙 검사

힙 검사란 힙 데이터 구조에 있는 요소의 개수를 확인하고 힙이 비어 있는지 여부를 검증하는 것을 의미합니다.

정렬이나 큐잉 작업을 할 때 힙을 검사하는 것은 중요합니다. `IsEmpty()`를 사용하여 처리할 요소가 있는지 확인하는 것도 중요합니다. 힙 크기는 Max-Heap 또는 Min-Heap 루트를 찾는 데 도움이 되므로, 힙 속성 뒤에 오는 요소의 개수를 알아야 합니다.

• 중량 – 힙의 크기 또는 길이를 반환합니다. 정렬된 상태로 저장된 요소의 개수를 알려줍니다.
• 비어있음 힙이 null이면 TRUE를 반환하고, 그렇지 않으면 FALSE를 반환합니다.

여기에서는 우선순위Q 루프를 실행한 다음 우선순위Q가 비어 있지 않은지 확인합니다.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

힙 데이터 구조의 사용

힙 데이터 구조는 다음과 같은 실생활의 많은 프로그래밍 응용 프로그램에서 유용하게 사용됩니다.

• 스팸 필터링에 도움이 됩니다.
• 다익스트라 알고리즘과 프림 알고리즘과 같은 그래프 알고리즘을 구현합니다.
• Opera시스템 부하 분산 및 데이터 압축.
• k번째로 작은 요소와 같은 순서 통계를 찾습니다.
• 리스트에서 항목을 로그 시간 복잡도로 검색할 수 있는 우선순위 큐를 구현합니다.
• 힙 데이터 구조는 힙 정렬을 통해 정렬하는 데에도 사용됩니다.
• 대기 줄에 선 고객들을 시뮬레이션합니다.
• 인터럽트 처리 Opera팅 시스템.
• 데이터 압축을 위한 허프만 코딩.
• AI 경로 계획에서 최적 우선 탐색 및 A* 휴리스틱 알고리즘을 지원합니다.

힙 우선순위 대기열 속성

다음 속성들은 힙 기반 우선순위 큐의 동작 방식을 설명합니다.

• 우선순위 힙에서는 리스트의 데이터 항목들을 서로 비교하여 더 작은 요소와 더 큰 요소를 결정합니다.
• 요소는 큐에 배치된 후 우선순위 순서대로 제거됩니다.
• 우선순위 큐의 모든 요소에는 우선순위를 나타내는 고유한 번호가 부여되어 있습니다.
• 우선순위 큐에서 나올 때, 가장 우선순위가 높은 요소가 먼저 나옵니다.

힙 우선순위 큐 구현 단계 Java

다음 섹션은 구체적인 내용으로 이어집니다. Java 이러한 규칙을 작동하는 코드로 변환하는 구현입니다.

힙 정렬 Java 과 Code 예시

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 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 과 Code 예시

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]

다음으로, 여러분은 다음 내용에 대해 배우게 될 것입니다. 이분법.

자주 묻는 질문