1. 힙(Heap)이란?

힙은 '우선순위 큐'를 구현하거나 '힙 정렬'을 하기 위해 사용하는 자료구조이다. 힙은 이진 힙(Binary Heap)이라고 부르기도 한며 둘은 동일한 개념이다. '우선순위 큐'란 특정 우선순위 기준을 가지고 만든 큐를 의미한다. 사실 기존의 큐 또한 우선순위 큐에 속한다. 기존의 큐는 삽입된 순서 기준으로 먼저 삽입된 것에 우선순위를 부여한 우선순위 큐이라고 할 수 있다.

2. 힙의 특징

힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나눌 수 있다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙이다. 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙이다. 아래부터는 최대 힙을 가정하고 힙에 대해 서술하고자 한다.

• 최소 힙 : 부모 노드의 값(key 값) ≤ 자식 노드의 값(key 값)
• 최대 힙 : 부모 노드의 값(key 값) ≥ 자식 노드의 값(key 값)

힙의 규칙은 다른 트리 자료구조들과 비교했을 때 비교적 간단하다. 힙은 큰 값이 위에 있고 작은 값들은 아래에 있는 트리로 느슨한 정렬 상태를 유지하는 트리이다. 힙은 완전 이진 트리이기에 삽입시 항상 왼쪽부터 채워지며 이진 탐색 트리와는 다르게 형제(같은 레벨의 노드)간 우선순위가 없다.

힙은 느슨한 정렬 상태를 유지하는 대신 항상 루트 노드는 가장 큰 값을 가진다. 따라서 이는 우선순위 큐를 사용하기에 아주 적합하다.

• 큰 값은 위에 있고 작은 값들은 아래에 있는 느슨한 정렬을 유지하는 트리
• 완전 이진 트리(=항상 왼쪽부터 채워지는 트리로 왼쪽 자식이 없는데 오른쪽 자식에 값이 있을 수 없다)
• 형제 노드간 우선우선순위는 없다.
• 루트 노드는 힙에서 가장 큰 값을 가진다.
• 배열을 통해 구현하기 쉽다.

힙은 완전 이진 트리이기에 중간에 데이터가 없는 빈 노드가 없어 배열로 쉽게 구현할 수 있다. 트리 형태를 배열로 구현하기 위해 다음과 같은 별도의 index 계산법을 사용한다.

노드	index
루트 노드	0
노드 자신	index
부모 노드	(index - 1) / 2
왼쪽 자식 노드	index * 2 + 1
오른쪽 자식 노드	index * 2 + 2

index를 0부터 시작한다고 했을 때의 경우이다. 오른쪽 자식노드의 경우 부모 노드 index를 구하기 위해 (자식index -1) / 2 식을 사용하면 소수점이 나오지만 index를 int형으로 선언시 소수점은 자동으로 버려지기에 부모 노드 index를 구할 수 있다.

index를 1부터 시작한다고 하면

• 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2
• 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1
• 부모 노드 인덱스 = 자식 노드 인덱스 / 2

이 된다.

데이터 삽입과 삭제의 경우 연산 자체는 O(1)의 시간 복잡도를 가지지만,
최대 또는 최소힙의 조건이 깨져 노드 위치를 바꾸는 과정이 필요하므로. 최종적으로 O(logN)의 시간 복잡도를 가진다.

3. 힙 구현

1. 인덱스 관련 코드

public class MaxHeap {
    Integer[] queue;
    final int ROOT_NODE_INDEX = 0;
    int size = 0; // 저장된 노드의 개수

    public MaxHeap(int length) {
        queue = new Integer[length];
    }

    private int getParentIndex(int index) {
        return (index - 1) / 2;
    }

    private int getLeftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int getRightChildIndex(int index) {
        return index * 2 + 2;
    }

    private boolean hasLeftChild(int index) {
        return size > getLeftChildIndex(index);
    }

    private boolean hasRightChild(int index) {
        return size > getRightChildIndex(index);
    }
    
    private void swap(int index1, int index2) {
        Integer tmp = queue[index1];
        queue[index1] = queue[index2];
        queue[index2] = tmp;
    }
    
    ...
    
    }

2. 힙 삽입

Heap의 삽입은 완전 이진 트리의 특성상 먼저 가장 왼쪽의(가장 마지막 index+1) 단말 노드에 새로운 노드를 삽입하고 해당 단말 노드에서부터 UpHeap을 진행한다. UpHeap이란 부모 노드와의 우선순위를 고려하여 부모 노드보다 우선순위가 높다면 부모 노드와 자식 노드의 위치를 바꾸는 것이다. UpHeap을 부모 노드보다 우선순위가 높지 않을 때까지 반복한다.

• 새로운 노드를 삽입할 수 있는 레벨에서 가장 왼쪽(가장 마지막 index + 1)의 단말 노드 위치로 삽입한다.
• 부모 노드와 우선순위를 비교하여 UpHeap
• 더 이상 부모 노드의 우선순위가 높지 않을 때 까지 2.반복

    public void add(Integer key) {
        if (queue.length == size)
            queue = Arrays.copyOf(queue, queue.length + 10);

        queue[size++] = key;
        upHeap(size - 1);
        System.out.println(key + " 삽입 완료");
    }

    public void upHeap(int index) {
        while (index != ROOT_NODE_INDEX && queue[index] > queue[getParentIndex(index)]) {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }

3. 힙 삭제

Heap의 목적은 가장 우선순위가 높은 데이터를 꺼내는 것이기에 Heap은 루트 노드만을 삭제할 수 있다. 삭제 연산시 루트 노드를 가장 마지막 index의 단말 노드와 교체하고(Key값만 교체) 부모 노드는 삭제할 노드인 해당 단말 노드와의 연결을 끊는다. 이후 루느 노드로 올라간 단말노드에 대해 DownHeap을 진행한다. DownHeap이란 자식 노드 중 우선순위가 높은 노드와 비교하여 자식 노드가 더 큰 key값을 갖는 경우 자리를 바꾸는 것을 말한다. 이를 자식 노드에 대해 계속해서 진행하여 더 이상 DownHeap이 불가할 때 까지 반복한다.

• 루트 노드의 key값을 가장 마지막 단말 노드의 key값과 교체
• 교체된 단말 노드를 삭제
• 새롭게 루트 노드가 된 노드는 자식 노드의 우선순위가 낮을 때까지 DownHeap 반복.

    public void delete() {
        int leafNodeIndex = size - 1;
        swap(ROOT_NODE_INDEX, leafNodeIndex);
        System.out.println(queue[leafNodeIndex] + " 삭제");
        queue[leafNodeIndex] = null;
        size--;
        DownHeap(ROOT_NODE_INDEX);

    }

    public void DownHeap(int index) {
        int childIndex;

        if(hasLeftChild(index))
            childIndex = getBiggerChildIndex(index);
        else
            return;

        while (size > index && hasLeftChild(index) && queue[index] < queue[childIndex]) {
            swap(index, childIndex);
            index = childIndex;
            childIndex = getBiggerChildIndex(index);
        }
    }

    private int getBiggerChildIndex(int index) {
        if (hasRightChild(index))
            return (queue[getLeftChildIndex(index)] >= queue[getRightChildIndex(index)]) ? getLeftChildIndex(index) : getRightChildIndex(index);
        else if (hasLeftChild(index))
            return getLeftChildIndex(index);
        else//자식 노드가 없는 단말 노드인 경우
            return -1;
    }

4. 자바에서 힙 사용

자바에서는 현재 PriorityQueue를 이용하여 최대 힙, 최소 힙을 간단하게 사용할 수 있도록 제공해주고 있다.

public void init()  throws IOException{
	PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    System.out.println("최소 힙");
    runHeapTest(minHeap);

	
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    System.out.println("최대 힙");
    runHeapTest(maxHeap);
}
	
private void runHeapTest(PriorityQueue<Integer> heap) {
	heap.add(1);
	heap.add(8);
	heap.add(5);
	heap.add(2);
	heap.add(3);
	while(!heap.isEmpty()) {
    	System.out.println(heap.poll());
    }
}

/* 출력
최소 힙
1
2
3
5
8
최대 힙
8
5
3
2
1
*/

하지만 보통 알고리즘을 풀다보면 이런 간단한 Integer값이 아니라 여러개의 값을 비교하여 최대, 최소를 구하라는 요구가 주어지고, 이를 위해서는 Object를 생성하여 추가를 해야한다. 이럴 경우 Comparable 또는 Comparator를 구현하여 생성한 Class(Object)를 PriorityQueue에서 사용할 수 있다.

간단한 예시로서 Rastaurant 라는 class에 Comparable를 Implement를 한 다음 출력을 위한 toString, compareTo를 구현한다. 그리고 위의 코드블럭에서 heap add 부분을 클레스로 add되도록 수정했다.

class Restaurant implements Comparable<Restaurant>{
	int grade;
	int distance;
	
	public Restaurant(int grade, int distance) {
		this.grade = grade;
		this.distance = distance;
	}
	
	public String toString() {
		return "grade : "+this.grade +" and distance :"+this.distance;
	}

    @Override
    public int compareTo(Restaurant target) {
    	if(this.grade == target.grade) {
    		return this.distance <= target.distance ? -1 : 1;
    	}
    	else {
    		return this.grade <= target.grade ? -1 : 1;
    	}
    }
}


------------------------------------------
public void init()  throws IOException{
	PriorityQueue<Restaurant> minHeap = new PriorityQueue<>();
    System.out.println("최소 힙");
    runHeapTest(minHeap);
    
    PriorityQueue<Restaurant> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    System.out.println("최대 힙");
    runHeapTest(maxHeap);
}
	
private void runHeapTest(PriorityQueue<Restaurant> heap) {
	heap.add(new Restaurant(1, 5));
	heap.add(new Restaurant(1, 4));
	heap.add(new Restaurant(2, 5));
	heap.add(new Restaurant(4, 3));
	heap.add(new Restaurant(4, 5));
	while(!heap.isEmpty()) {
    	System.out.println(heap.poll().toString());
    }
}

/* 출력
최소 힙
grade : 1 and distance : 4
grade : 1 and distance : 5
grade : 2 and distance : 5
grade : 4 and distance : 5
grade : 4 and distance : 5
최대 힙
grade : 4 and distance : 5
grade : 4 and distance : 4
grade : 2 and distance : 4
grade : 1 and distance : 4
grade : 1 and distance : 4
*/

위에 @Override된 결과문에서 (return this.distance <= target.distance ? -1 : 1;) 해당부분에 더 작으면 -1 (우선순위 업), 크면 1(우선순위 다운)을 리턴하는 결과를 가지고 priorityQueue가 동작하게 된다. (Collections.reverseOrder() 선언은 반대)

만약 코드상에 Collections.reverseOrder() 를 선언하고 싶지않다면 Comparable에서 -1 을 1로 1을 -1로 변경해주면 최대힙의 결과를 동일하게 볼 수 있다.