힙 데이터 구조: 힙이란 무엇입니까? 최소 및 최대 힙(예)

힙이란 무엇입니까?

힙은 특수 트리 데이터 구조입니다. 힙은 루트(부모)라고 하는 최상위 노드로 구성됩니다. 두 번째 자식은 루트의 왼쪽 자식이고, 세 번째 노드는 루트의 오른쪽 자식입니다. 연속적인 노드는 왼쪽에서 오른쪽으로 채워집니다. 부모 노드 키는 자식의 키와 비교되고 적절한 배열이 발생합니다. 트리는 각 엔터티를 노드라고 하는 곳에서 시각화하기 쉽습니다. 노드에는 식별을 위한 고유한 키가 있습니다.

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

힙 데이터 구조를 사용하는 주요 이유는 다음과 같습니다.

  • 힙 데이터 구조는 로그 시간(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의 구조에서 루트 노드(상위)는 노드의 하위 노드와 같거나 큰 값을 갖습니다.
  • 힙 검사는 힙 데이터 구조의 요소 수를 확인하고 힙이 비어 있는지 확인하는 것을 의미합니다.