Java에서 최소 힙 구현

최소 힙은 각 내부 노드의 값이 해당 노드의 자식 값보다 작거나 같은 완전한 이진 트리입니다.
힙의 요소를 배열로 매핑하는 것은 간단합니다. 노드가 인덱스 n에 저장되면 왼쪽 자식은 인덱스 2n+1에, 오른쪽 자식은 인덱스 2n+2에 저장됩니다.

예시

최소 힙 표현

최소 힙은 일반적으로 배열로 표시됩니다.
루트가 Arr[] 인 어레이 Arr[0]를 고려하십시오. 임의의 i번째 노드, 즉 Arr[i]에 대해:

Arr[(i -1) / 2]는 상위 노드를 반환합니다.

Arr[(2 * i) + 1]는 왼쪽 자식 노드를 반환합니다.

Arr[(2 * i) + 2]는 오른쪽 자식 노드를 반환합니다.

최소 힙에 대한 작업

getMin(): Min Heap의 루트 요소를 반환합니다. 이 작업의 시간 복잡도는 O(1)입니다.

extractMin(): MinHeap에서 최소 요소를 제거합니다. 이 작업의 시간 복잡도는 O(Log n)입니다. 이 작업은 루트를 제거한 후 (heapify()를 호출하여) 힙 속성을 유지해야 하기 때문입니다.

insert(): 새 키를 삽입하는 데 O(Log n) 시간이 걸립니다. 트리 끝에 새 키를 추가합니다. 새 키가 부모 키보다 크면 아무 것도 할 필요가 없습니다. 그렇지 않으면 위반된 힙 속성을 수정하기 위해 위로 트래버스해야 합니다.

우선 순위 대기열을 사용하여 Java에서 최소 힙 구현

Java에서 PriorityQueue 클래스를 사용하여 최소 힙을 구현하는 방법은 다음과 같습니다. 기본적으로 Min Heap은 이 클래스에 의해 구현됩니다.

import java.util.*;
public class MinHeap {
    static PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    public static void main(String args[]) {

        // Adding elements using add()
        minHeap.add(8);
        minHeap.add(5);
        minHeap.add(13);
        minHeap.add(2);
        minHeap.add(23);
        minHeap.add(16);

        // Displaying minHeap elements
        print();

        // Find number of elements using size()
        System.out.println("Size of heap = "+minHeap.size());

        // View head using peek()
        System.out.println("Head = "+minHeap.peek());

        // Remove head and modify Heap using poll()
        minHeap.poll();
        System.out.println("Heap after removing head");
        print();

        // Remove specific element using remove()
        minHeap.remove(8);
        System.out.println("Heap after removing 8");
        print();

        // Check if an element is present using contains()
        boolean flag=minHeap.contains(15);
        System.out.println("Does heap contain element 15? " +flag);

        System.out.println("Size of heap = "+minHeap.size());
    }
    public static void print() {
        System.out.print("Min Heap : ");
        for(Integer i:minHeap)
            System.out.print(i+" ");
        System.out.println("\n");
    }
}

산출

Min Heap : 2 5 13 8 23 16 

Size of heap = 6
Head = 2
Heap after removing head
Min Heap : 5 8 13 16 23 

Heap after removing 8
Min Heap : 5 16 13 23