웹사이트 검색

Java에서 최대 힙 데이터 구조 구현


최대 힙은 노드 값이 자식 값보다 크거나 같은 완전한 이진 트리입니다. Max Heap 데이터 구조는 힙 정렬을 사용하여 데이터를 정렬하는 데 유용합니다.

이 튜토리얼에서는 Java에서 처음부터 최대 힙을 구현하기 위해 알아야 할 모든 것을 다룰 것입니다.

Java에서 최대 힙 데이터 구조 구현

배열을 사용하여 힙을 나타냅니다. 힙은 완전한 이진 트리이므로 공간 낭비가 없습니다.

예를 들어 다음과 같은 힙을 생각해 봅시다.

배열 표현은 다음과 같습니다.

최대 힙 선언은 다음과 같이 수행됩니다.

 static class MaxHeap {
        private int[] Heap; // array 
        private int size;
        private int maxsize; 

        public MaxHeap(int size) {
            this.maxsize = size;
            this.size = 0;
            Heap = new int[this.maxsize + 1];
            Heap[0] = Integer.MAX_VALUE;
        }

힙은 최대 힙을 저장하는 배열입니다. 생성자는 크기를 가져오고 0번째 요소를 무한대로 사용하여 배열을 초기화합니다. 인덱스 1에서 힙을 시작합니다.

1. 노드의 부모 가져오기

힙을 배열로 저장하므로 노드의 부모를 가져오는 것이 더 쉬워집니다.

위치 i에 있는 요소의 경우 부모의 위치는 다음과 같이 지정됩니다.

(i)/2

구현하는 동안 다음을 사용하여 부모를 얻을 수 있습니다.

private int parent(int pos) {
            return pos / 2;
        }

2. 노드의 자식 가져오기

위치 i에 있는 노드의 경우 자식은 다음 공식으로 제공됩니다.

왼쪽 자식:

(2*i)

오른쪽 자식 :

(2*i)+ 1

참고: 이것은 힙이 인덱스 1에서 시작하는 경우에 해당합니다. 힙이 위치 0에서 시작하는 경우 값은 각각 왼쪽 및 오른쪽 자식에 대해 (2*i) +1 및 (2*i) +2입니다. .

코드에서 다음과 같이 구현합니다.

  private int leftChild(int pos) {
            return (2 * pos) ;
        }

  private int rightChild(int pos) {
            return (2 * pos) + 1;
        }

3. 새로 삽입된 요소를 힙화

요소를 힙에 삽입한 후 힙 속성을 충족하지 못할 수 있습니다. 이 경우 힙의 위치를 조정하여 다시 힙으로 만들어야 합니다. 이 프로세스를 Heapifying이라고 합니다.

최대 힙의 요소를 힙화하려면 자식의 최대값을 찾아 현재 요소와 교체해야 합니다. 각 노드에서 힙 속성이 만족될 때까지 이 프로세스를 계속합니다.

heapify하기 위해 우리는 뿌리에서 잎으로 이동합니다. 따라서 이것은 Down Heapify라고도 합니다.

주목해야 할 또 다른 흥미로운 점은 리프가 아닌 노드에서만 다운 힙화를 수행한다는 것입니다.

down-heapify 함수의 코드는 다음과 같습니다.

 private void downHeapify(int pos) {

//checking if the node is a leaf node 
            if (pos >= (size / 2) && pos <= size)
                return;

//checking if a swap is needed
            if (Heap[pos] < Heap[leftChild(pos)] ||
                    Heap[pos] < Heap[rightChild(pos)]) {

//replacing parent with maximum of left and right child 
                if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
                    swap(pos, leftChild(pos));

//after swaping, heapify is called on the children 
                    downHeapify(leftChild(pos));
                } else {

                   swap(pos, rightChild(pos));
//after swaping, heapify is called on the children 
                    downHeapify(rightChild(pos));
                }
            }
        }

스왑 기능은 다음과 같습니다.

   private void swap(int fpos, int spos) {
            int tmp;
            tmp = Heap[fpos];
            Heap[fpos] = Heap[spos];
            Heap[spos] = tmp;
        }

재귀 대신 while 루프를 사용하여 동일한 코드를 작성할 수도 있습니다.

down-heapify에서 우리는 부모에서 자식으로 이동했습니다. 상향식으로도 움직일 수 있습니다. 상향식 방식으로 이동할 때 노드를 부모 노드와 비교합니다. 이것을 업 히피파이라고 합니다.

up-heapify의 코드는 다음과 같습니다.

  private void heapifyUp(int pos) {
            int temp = Heap[pos];
            while(pos>0 && temp > Heap[parent(pos)]){
                Heap[pos] = Heap[parent(pos)];
                pos = parent(pos);
            }
            Heap[pos] = temp;
        }

재귀 대신 while 루프를 사용하여 heapify를 위한 코드를 작성했습니다.

4. 새 노드 삽입

배열 끝에 새 요소가 추가되고 힙 속성이 유지되도록 스왑이 수행됩니다.

삽입 알고리즘은 다음과 같습니다.

  1. 힙 크기 늘리기
  2. 힙(배열) 끝에 새 요소 유지
  3. 아래에서 위로 쌓기

삽입 코드는 다음과 같습니다.

 public void insert(int element) {
            Heap[++size] = element; 
            int current = size;
            heapifyUp(current);
        }

5. 노드 삭제/추출

힙에서 노드를 삭제/추출하려면 루트에서 요소를 삭제합니다. 루트는 항상 최대 요소를 제공합니다.

삭제 알고리즘은 다음과 같습니다.

  1. 첫 번째 요소를 변수에 복사합니다.
  2. 마지막 요소를 첫 번째 위치(루트)에 복사합니다.
  3. downHeapify()를 호출합니다.

삭제 코드는 다음과 같습니다.

  public int extractMax() {
            int max = Heap[1];
            Heap[1] = Heap[size--];
            downHeapify(1);
            return max;
        }

여기서 우리는 size--를 사용하여 힙의 크기를 줄입니다.

Java에서 최대 힙 구현 완료

Max Heap의 전체 Java 구현은 다음과 같습니다.

package com.JournalDev;

public class Main {
    static class MaxHeap {
        private int[] Heap;
        private int size;
        private int maxsize;

        public MaxHeap(int size) {
            this.maxsize = size;
            this.size = 0;
            Heap = new int[this.maxsize + 1];
            Heap[0] = Integer.MAX_VALUE;
        }

        private int parent(int pos) {
            return pos / 2;
        }

        private int leftChild(int pos) {
            return (2 * pos)  ;
        }

        private int rightChild(int pos) {
            return (2 * pos) + 1;
        }


        private void swap(int fpos, int spos) {
            int tmp;
            tmp = Heap[fpos];
            Heap[fpos] = Heap[spos];
            Heap[spos] = tmp;
        }

        private void downHeapify(int pos) {
            if (pos >= (size / 2) && pos <= size)
                return;

            if (Heap[pos] < Heap[leftChild(pos)] ||
                    Heap[pos] < Heap[rightChild(pos)]) {

                if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) {
                    swap(pos, leftChild(pos));
                    downHeapify(leftChild(pos));
                } else {
                    swap(pos, rightChild(pos));
                    downHeapify(rightChild(pos));
                }
            }
        }
        private void heapifyUp(int pos) {
            int temp = Heap[pos];
            while(pos>0 && temp > Heap[parent(pos)]){
                Heap[pos] = Heap[parent(pos)];
                pos = parent(pos);
            }
            Heap[pos] = temp;
        }


        public void insert(int element) {
            Heap[++size] = element;


            int current = size;
            heapifyUp(current);

        }

        public void print() {
            for (int i = 1; i <= size / 2; i++) {
                System.out.print(+ Heap[i] + ": L- " +
                        Heap[2 * i] + " R- " + Heap[2 * i + 1]);
                System.out.println();
            }
        }

        public int extractMax() {
            int max = Heap[1];
            Heap[1] = Heap[size--];
            downHeapify(1);
            return max;
        }
    }
    public static void main(String[] arg)
    {
      
        MaxHeap maxHeap = new MaxHeap(15);
        maxHeap.insert(1);
        maxHeap.insert(4);
        maxHeap.insert(2);
        maxHeap.insert(5);
        maxHeap.insert(13);
        maxHeap.insert(6);
        maxHeap.insert(17);

        maxHeap.print();
        System.out.println("The max is " + maxHeap.extractMax());
    }

} 

Output : 

17: L- 5 R- 13
5: L- 1 R- 4
13: L- 2 R- 6
The max is 17

결론

이 튜토리얼은 Java의 최대 힙 데이터 구조에 관한 것입니다.