Java에서 최소-최대 힙 구현

1. Java의 최소-최대 힙 소개
2. Java에서 PriorityQueue 클래스 및 Collections.reverseOrder()를 사용하여 Max-Heap 구현
3. Java의 PriorityQueue 클래스로 최소 힙 구현

이 기사에서는 PriorityQueue 클래스를 사용하여 최대 힙 및 최소 힙을 구현합니다. 또한 힙에서 요소를 삽입 및 삭제하는 방법도 보여줍니다.

Java의 최소-최대 힙 소개

힙은 트리를 기반으로 하는 데이터 구조이며 완전한 이진 트리를 형성합니다. 힙은 배열로 표시됩니다. 힙에는 최소 힙과 최대 힙의 두 가지 유형이 있습니다. 최소 힙이라고도 하는 최소 힙은 루트 노드 또는 상위 노드에서 가장 작은 값을 갖습니다. 마찬가지로 max-heap은 루트 노드 또는 상위 노드에서 가장 큰 값을 갖습니다. 따라서 힙 데이터 구조를 사용하면 배열에서 가장 큰 요소와 가장 작은 요소를 쉽게 추출할 수 있습니다. O(1)에서 가장 큰 요소와 가장 작은 요소를 얻을 수 있습니다. 힙에서 요소를 제거하거나 힙에서 삽입하는 복잡성은 O(log N)입니다.

최소-최대 힙은 최소 및 최대 수준이 교대로 포함된 데이터 구조입니다. 루트 노드는 가장 작은 값을 포함하고 그 아래의 다음 레벨은 가장 큰 값을 나타냅니다. 최소값은 0, 2, 4와 같은 짝수 레벨로 표시됩니다. 1, 3, 5와 같은 홀수 레벨은 최대값을 나타냅니다.

Java에서 PriorityQueue 클래스 및 Collections.reverseOrder()를 사용하여 Max-Heap 구현

PriorityQueue 클래스를 사용하여 Java에서 힙을 구현할 수 있습니다. 클래스는 기본적으로 최소 힙을 구현하며 컬렉션의 reverseOrder() 메서드를 사용하여 최대 힙을 구현할 수 있습니다. peek() 메서드를 사용하여 힙에 있는 루트 노드의 요소를 표시할 수 있습니다. poll() 메서드는 루트 노드에서 값을 반환하고 제거합니다. contains() 메서드를 사용하여 요소가 힙에 존재하는지 확인할 수 있습니다.

예를 들어 java.util 패키지에서 모든 것을 가져옵니다. MaxHeap 클래스를 만들고 기본 메서드를 작성합니다. 그런 다음 PriorityQueue 클래스의 인스턴스를 pq로 만듭니다. 제네릭 유형을 사용하여 정수 인스턴스를 생성합니다. 객체 생성 시 괄호 안에 Collections.reverseOrder()를 작성합니다. add() 메서드를 사용하여 4개의 정수 값을 추가합니다. 객체 pq로 peek() 메소드를 호출하고 인쇄하십시오. 그런 다음 객체에서 poll() 메서드를 사용합니다. 다음으로 remove() 메소드를 매개변수로 값 30으로 호출한 다음 iterator() 및 hasNext() 메소드를 사용하여 배열의 요소를 인쇄합니다. 마지막으로 20 매개변수와 함께 contains() 메서드를 사용합니다.

아래 예에서 import java.util.*은 최대 힙을 생성하는 데 사용한 PriorityQueue 클래스를 가져옵니다. 1, 2, 3, 4 값을 힙에 추가했습니다. peek() 메서드는 힙에서 가장 큰 값 4를 반환했습니다. 그런 다음 poll() 메소드는 최대 수 4를 제거했습니다. 그런 다음 remove() 메서드를 사용하여 3이라는 숫자를 제거하고 나머지 요소를 힙에 인쇄했습니다. 3과 4를 이미 제거했기 때문에 1과 2 값을 출력했습니다. 마지막으로 contains() 메서드를 사용하여 힙에 숫자 2가 포함되어 있는지 확인했습니다. 힙에 숫자가 있으므로 true를 반환했습니다. 따라서 Collectios.reverseOrder()를 사용하여 PriorityQueue 클래스를 사용하여 최대 힙을 구현했습니다.

예제 코드:

import java.util.*;

class MaxHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr3.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(2);
    System.out.println("Does the heap contains 2 ?" + b);
  }
}

출력:

The highest value in the heap:4
after removing 3:
2
1
Does the heap contains 2 ?true

Java의 PriorityQueue 클래스로 최소 힙 구현

PriorityQueue 클래스는 기본적으로 최소 힙을 구현합니다. 우리는 최대 힙에 대해 했던 것과 동일한 구현 방법을 최소 힙에 적용합니다. peek(), remove(), poll() 및 contains()와 같은 동일한 방법을 사용하여 동일한 작업을 수행합니다.

아래 예에서는 1, 2, 3, 4라는 숫자를 힙에 추가했습니다. peek() 메서드는 루트 노드의 요소를 반환했으며 출력에 표시된 대로 1입니다. poll() 메소드를 사용하여 루트 노드 요소 1을 제거했습니다. remove() 함수를 사용하여 힙에서 3 값을 다시 제거했습니다. 이 값을 제거한 후 힙에는 2 및 4 요소만 포함됩니다. 마지막으로 contains() 메소드를 사용하여 힙에서 3 값을 확인했습니다. 이미 제거했으므로 이 메서드는 false 값을 반환합니다. 따라서 PriorityQueue 클래스를 사용하여 최소 힙을 구현했습니다.

예제 코드:

import java.util.*;

class MinHeap {
  public static void main(String args[]) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);
    System.out.println("The highest value in the heap:" + pq.peek());
    pq.poll();
    pq.remove(3);
    System.out.println("after removing 3:");
    Iterator<Integer> itr = pq.iterator();
    while (itr.hasNext()) System.out.println(itr.next());
    boolean b = pq.contains(3);
    System.out.println("Does the heap contains 3 ?" + b);
  }
}

출력:

The highest value in the heap:1
after removing 3:
2
4
Does the heap contains 2 ?false