배열(Array)을 이용한 힙(Heap) 구현

힙(Heap)은 배열 또는 연결 리스트(Linked List)로 구현할 수 있다. 연결 리스트 보다는 배열로 구현하는 것이 연산시 노드를 탐색하는 과정에서 비교적 간단하여 배열로 구현했다. 연결 리스트로 구현하는 경우 인덱스가 비교적 복잡해진다.

Cf. 리스트로 구현하면 `resize()` 메서드를 따로 둘 필요가 없어진다. `capacity`값도 마땅히 필요하지 않아진다.

Cf. 리스트로 구현하면 인덱스는 0 이상 `this.size` 미만이며, 자식 노드는 특정 노드의 인덱스가 \(n\)이라면, \(n * 2 + 1\), \(n * 2 + 2\)가 된다.

필요시 참고용도로 리스트로 힙을 구현하는 코드를 일부 작성해두신 분의 블로그 게시글 링크를 첨부한다.

 

---

전체 코드

(최소힙을 구현하여 루트값이 가장 작은 형태입니다.)

package DataStructure;

import java.util.NoSuchElementException;
import java.util.Random;

/**
 * 배열을 이용한 최소힙(Heap) 구현
 * - 배열로 구현하기 위해 제네릭 사용하지 않음
 *
 * 주요 기능
 * add 노드 추가
 * delete 루트 노드 삭제
 * peak 루트 노드 조회
 * swap 노드 위치 교환
 */
public class HeapExample1 {

    public static void main(String[] args) {
        Random random = new Random();
        Heap h = new Heap(10);

        for (int i = 0; i < 10; i++) {
            int n = random.nextInt(19) + 1; // 1 ~ 20
            h.add(n);
        }

        System.out.println("최초 heap: " + h);
        System.out.println("peek: " + h.peek());

        h.add(12);
        System.out.println("12 삽입 후 heap: " + h);
        h.add(5);
        System.out.println("5 삽입 후 heap: " + h);

        h.delete();
        System.out.println("힙 데이터 삭제 후 heap: " + h);

        h.delete();
        System.out.println("힙 데이터 삭제 후 heap: " + h);
    }

    protected static class Heap {
        int capacity = 0;
        int size = 0;
        int[] heap = null;

        public Heap(int capacity) {
            this.capacity = capacity;
            this.heap = new int[capacity + 1];
        }

        public void resize(int capacity) {
            if (this.size > capacity) {
                throw new IllegalArgumentException("힙의 크기보다 작아질 수는 없습니다.");
            }
            int[] newHeap = new int[capacity];
            for (int i = 1; i <= this.size; i++) {
                newHeap[i] = this.heap[i];
            }

            this.heap = newHeap;
        }

        private void add(int node) {
            if (this.size + 1 > this.capacity) {
                resize(this.size * 2); // 용량 초과시 2배로 증가
            }
            this.heap[this.size + 1] = node;
            this.size++;

            // 들어가야 하는 위치 찾기
            // (this.size + 1) / 2 = 들어갈 부모의 인덱스
            int nodeIdx = this.size + 1;
            int parentIdx = nodeIdx / 2;

            while (this.heap[parentIdx] > node && nodeIdx > 1) {
                swap(parentIdx, nodeIdx);

                // 바뀐 인덱스
                nodeIdx = parentIdx;
                parentIdx = nodeIdx / 2;
            }
        }

        private void delete() {
            if (this.size == 0 || this.heap[1] == 0) {
                throw new NoSuchElementException();
            }

            // root 제거 -> root 자리에 last node 옮김
            this.heap[1] = this.heap[this.size];
            this.size--;

            int nodeIdx = 1;

            int targetIdx;
            while ((nodeIdx * 2 <= this.size && this.heap[nodeIdx * 2] < this.heap[nodeIdx])
                    || (nodeIdx * 2 + 1) <= this.size && this.heap[nodeIdx * 2 + 1] < this.heap[nodeIdx]) {
                int childIdx0 = nodeIdx * 2;
                int childIdx1 = nodeIdx * 2 + 1;
                // 비교값 유효성 검증
                if (childIdx0 <= this.size && childIdx1 > this.size) {
                    targetIdx = childIdx0;
                } else if (childIdx1 <= this.size && childIdx0 > this.size) {
                    targetIdx = childIdx1;
                } else {
                    targetIdx = this.heap[childIdx0] <= this.heap[childIdx1] ? childIdx0 : childIdx1;
                }

                if (this.heap[nodeIdx] > this.heap[targetIdx]) {
                    swap(nodeIdx, targetIdx);

                    nodeIdx = targetIdx;
                }
            }
        }

        private int peek() {
            if (heap[1] == 0) {
                throw new NoSuchElementException();
            }

            return heap[1];
        }

        private void swap(int idx0, int idx1) {
            int val = this.heap[idx0];
            this.heap[idx0] = this.heap[idx1];
            this.heap[idx1] = val;
        }

        private int getSize() {
            return this.size;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            for(int i = 1; i <= this.size; i++) {
                int val = this.heap[i];
                builder.append(val + ", ");
            }

            if (!builder.toString().isEmpty()) {
                builder.delete(builder.length() - 2, builder.length());
            }

            return "[" + builder + "]";
        }
    }
}

 

---

주요 필드 & 생성자

class Heap {
    int capacity = 0; // 용량
    int size = 0; // 크기(노드의 수)
    int[] heap = null; // 실제 데이터를 저장하는 배열

	// 생성시 용량을 입력받음
    public Heap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity + 1];
        // 편의를 위해 인덱스는 1부터 시작(부모-자식 노드간의 인덱스 계산에 용이)
    }
}

 

---

주요 메서드

resize

public void resize(int capacity) {
	if (this.size > capacity) {
		throw new IllegalArgumentException("힙의 크기보다 작아질 수는 없습니다.");
	}
    
	int[] newHeap = new int[capacity];
	for (int i = 1; i <= this.size; i++) {
		newHeap[i] = this.heap[i];
	}

	this.heap = newHeap;
}

데이터 추가 삽입을 하고자 할 때 배열의 크기가 한계에 이르렀을 때 배열의 크기를 키워준다. (크기가 큰 새로운 배열을 생성해 노드를 옮겨담는다.) 아래 코드에서는 2배로 증가시키고 있다.

 

add

private void add(int node) {
    if (this.size + 1 > this.capacity) {
        resize(this.size * 2); // 용량 초과시 2배로 증가
    }
    this.heap[this.size + 1] = node;
	this.size++;

    // 들어가야 하는 위치 찾기
    // (this.size + 1) / 2 = 들어갈 부모의 인덱스
    int nodeIdx = this.size + 1;
    int parentIdx = (nodeIdx) / 2;

    while (this.heap[parentIdx] > node && nodeIdx > 1) {
        swap(parentIdx, nodeIdx);

        // 바뀐 인덱스
        nodeIdx = parentIdx;
        parentIdx = nodeIdx / 2;
    }
}

1. 노드 삽입시 가장 먼저 현재 힙의 용량에 넣을 수 있는지를 확인한 후 용량이 꽉 찬 경우 힙의 크기를 늘리는 과정을 수행한다.

2. 노드를 가장 마지막 노드로 추가한다. (힙의 size를 증가시킨다.) 더불어 부모 노드의 위치를 찾는다.

3. 부모노드값보다 새로 삽입된 값이 더 작다면 부모노드와의 위치 교환을 수행한다. 이 때 노드 자신의 위치(인덱스)와 부모 인덱스가 변경된 후 while문이 다시 돌아야 한다.

Cf. while문의 조건에 parentIdx와 관련된 로직을 넣지 않은 것은 다음과 같다.

ㄱ. 가장 최후에는 대상 노드의 인덱스가 1(root에 위치), 부모 노드 인덱스가 0이 되는 경우이다.

ㄴ. `this.heap[0]`은 기본적으로 0이고, 이 힙의 기능을 테스트하기 위한 HeapExample.main()에는 1이상 20 이하의 자연수만 들어가도록 했기 때문에 늘 `this.heap[0] < this.heap[1]`이 되기 때문에 해당 while문이 종료된다.

 

delete

private void delete() {
    if (this.size == 0 || this.heap[1] == 0) {
        throw new NoSuchElementException();
    }

    // root 제거 -> root 자리에 last node 옮김
    this.heap[1] = this.heap[this.size];
    this.size--;

    int nodeIdx = 1;

    int targetIdx;
    while ((nodeIdx * 2 <= this.size && this.heap[nodeIdx * 2] < this.heap[nodeIdx])
            || (nodeIdx * 2 + 1) <= this.size && this.heap[nodeIdx * 2 + 1] < this.heap[nodeIdx]) {
        int childIdx0 = nodeIdx * 2;
        int childIdx1 = nodeIdx * 2 + 1;
        // 비교값 유효성 검증
        if (childIdx0 <= this.size && childIdx1 > this.size) {
            targetIdx = childIdx0;
        } else if (childIdx1 <= this.size && childIdx0 > this.size) {
            targetIdx = childIdx1;
        } else {
            targetIdx = this.heap[childIdx0] <= this.heap[childIdx1] ? childIdx0 : childIdx1;
        }

        if (this.heap[nodeIdx] > this.heap[targetIdx]) {
            swap(nodeIdx, targetIdx);

            nodeIdx = targetIdx;
        }
    }
}

1. 힙이 비어있는지(최소 하나의 노드가 존재하는지) 확인하고 없는 경우 `NoSuchElementException()`을 수행한다. `this.size > 0`으로 확인해도 된다.

2. 루트 노드 자리에 가장 마지막 노드를 옮긴다. (루트 노드는 그대로 삭제된다.) 힙의 사이즈가 감소한다.

3. 루트 노드 자리로 옮긴 대상 노드를 자식 노드와 비교 및 정렬하는 과정을 거친다. 이 때 노드 자신의 위치(인덱스)와 자식 노드의 인덱스가 변경된 경우 인덱스 값 변경 후 while문이 다시 돌아야 한다.

• 자식 노드(가 존재할 수 있는) 인덱스는 부모 노드 인덱스가 \(n\)이라고 할 때, 항상 \(n * 2\)(왼쪽 노드), \(n * 2 + 1\)(오른쪽 노드)이다.
• 자식 노드 인덱스를 가지고 실제로 자식 노드가 존재하는지 확인하기 위해서 자식 노드 인덱스들이 힙의 크기보다 작거나 같은지(Cf. 1 <= 힙의 인덱스 <= this.size) 확인한다.
• 자식 노드 중 값이 더 작은 노드(둘 다 존재하면 비교, 둘 중 한 쪽만 존재하면 바로 부모와 비교)를 부모 노드 값과 비교하여 부모 노드보다 더 작으면(최소힙이기 때문) 위치를 변경하는 것을 반복한다.

 

---

peak

private int peek() {
    if (heap[1] == 0) {
        throw new NoSuchElementException();
    }

    return heap[1];
}

힙이 비어있는지 확인하는 것까지는 `delete()`와 동일하지만 이후에 삭제 및 정렬 과정이 생략되고 루트 노드를 반환한다.

 

---

swap

private void swap(int idx0, int idx1) {
    int val = this.heap[idx0];
    this.heap[idx0] = this.heap[idx1];
    this.heap[idx1] = val;
}

배열에서 특정 값들의 위치를 변경하듯 하면 된다.

 

---

toString 오버라이드

해당 기능은 단순히 힙의 노드 목록을 출력하기 위해서 구현한 것으로, 주요 기능에서 제외했습니다.

@Override
public String toString() {
    StringBuilder builder = new StringBuilder();
    for(int i = 1; i <= this.size; i++) {
        int val = this.heap[i];
        builder.append(val + ", ");
    }

    if (!builder.toString().isEmpty()) {
        builder.delete(builder.length() - 2, builder.length());
    }

    return "[" + builder + "]";
}