Heap 자료구조

힙은 힙에 있는 요소의 순서를 보장하는 속성인 힙 속성을 만족하는 트리 기반 데이터 구조입니다. 최대 힙에서 부모 노드는 항상 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 항상 자식 노드보다 작거나 같습니다. 이렇게 하면 일정한 시간에 힙에서 최대 또는 최소 요소를 쉽게 찾을 수 있습니다.

힙은 일반적으로 배열을 사용하여 구현되며 배열의 각 요소는 힙의 노드에 해당합니다. 루트 노드는 인덱스 0에 있고 인덱스 i에 있는 노드의 자식은 인덱스 2i+1 및 2i+2에 있습니다. 반대로 인덱스 i에 있는 노드의 부모 노드는 인덱스 (i-1)/2에 있습니다. 이 구조는 힙의 효율적인 순회 및 조작을 허용합니다.

힙은 일반적으로 힙 정렬, 우선 순위 큐, Dijkstra의 알고리즘 및 Prim의 알고리즘과 같은 그래프 알고리즘과 같은 알고리즘에서 사용됩니다. 우선 순위 대기열에서 힙은 우선 순위에 따라 요소의 순서를 유지하는 데 사용되는 반면, 그래프 알고리즘에서는 힙이 소스 노드에서 그래프의 다른 노드까지의 최소 가중치 또는 거리를 추적하는 데 사용됩니다.

힙에는 최대 힙과 최소 힙의 두 가지 유형이 있습니다. 최대 힙에서는 루트 노드의 값이 가장 크고 최소 힙에서는 루트 노드의 값이 가장 작습니다. 두 유형의 힙은 동일한 구조를 갖지만 요소의 순서는 다릅니다.

힙에서 수행할 수 있는 작업에는 삽입, 최소 또는 최대 요소 추출, 요소 삭제 및 요소 값 업데이트가 포함됩니다. 이러한 작업은 일반적으로 O(log n) 시간이 걸립니다. 여기서 n은 힙의 요소 수입니다.

전반적으로 힙은 최대 또는 최소 요소에 대한 효율적인 액세스를 제공하는 강력한 데이터 구조이므로 다양한 응용 프로그램에 유용합니다.

다음은 힙 데이터 구조를 사용하여 n 정수 배열에서 상위, 최대, 최소 및 n번째 요소를 찾는 Java 코드의 두 가지 예입니다.

상위, 최대 및 최소 요소 찾기

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        int[] nums = { 10, 5, 8, 3, 2, 6, 4, 7, 9, 1 };
        int k = 3; // find top 3 elements

        // Use a max heap to find the top k elements
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) {
            maxHeap.add(num);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }

        // Print the top k elements
        System.out.println("Top " + k + " elements:");
        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll());
        }

        // Use a min heap to find the minimum element
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
        }

        // Print the minimum and maximum elements
        System.out.println("Minimum element: " + minHeap.peek());
        System.out.println("Maximum element: " + maxHeap.peek());
    }
}

n번째 요소 찾기

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        int[] nums = { 10, 5, 8, 3, 2, 6, 4, 7, 9, 1 };
        int n = 7; // find the 7th element

        // Use a min heap to find the nth element
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > n) {
                minHeap.poll();
            }
        }

        // Print the nth element
        System.out.println("The " + n + "th element is: " + minHeap.peek());
    }
}