[자료구조] 힙

힙 (Heap)

힙의 개념

• 힙 (Heap) : 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록(우선순위 큐를 위해) 만들어진 자료구조

 

힙의 특징

• 완전 이진 트리의 일종
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리
• key(부모 노드) >= key(자식 노드)
• 중복된 값을 허용
• 반정렬 상태(느슨한 정렬 상태) 유지
• 큰 값이 상위 레벨이 있고 작은 값이 하위 레벨에 있음
• 삭제 연산이 수해오딜 때마다 가장 큰 값을 찾아내기만 하면 되므로 전체를 정렬할 필요 없음
• 시간 복잡도 : O(logn)

 

우선순위 큐 (Priority Queue)

• 큐에 우선순위라는 개념 접목
• 우선순위가 높은 데이터가 먼저 나감
• 힙, 배열, 연결리스트로 구현 가능하며 힙으로 구현하는 것이 가장 효율적

 

힙의 종류

최대 힙 (Max Heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모 노드) >= key(자식 노드)

 

최소 힙 (Min Heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모 노드) <= key(자식 노드)

 

힙의 연산

• 배열로 구현할 경우 부모 노드의 인덱스를 1부터 시작하여 왼쪽 자식 노드부터 순서대로 2, 3, .. 부여
• (부모 노드의 인덱스) = (자식 노드의 인덱스) / 2
• (왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2
• (오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 + 1

 

삽입 연산

1. 힙 크기를 하나 증가시킴
2. 새로운 노드를 힙의 번호순으로 마지막 위치(증가된 힙 크기 위치)에 삽입
3. 부모 노드와 비교하여 새로운 노드가 더 크면 교환
4. 새로운 노드가 부모 노드보다 작으면 더이상 교환하지 않음

 

삭제 연산

1. 루트 노드 반환하고 삭제함
2. 말단 노드를 루트 노드로 옮김
3. 힙 크기를 하나 줄임
4. 자식 노드와 비교하여 자식 노드가 더 크면 교환
5. 자식 노드가 부모 노드보다 작으면 더이상 교환하지 않음

 

힙의 구현

• 최소 힙 (Min Heap)

public class MinHeap {

	private ArrayList<Integer> minHeap;

	public MinHeap() {
		minHeap = new ArrayList<>();
		minHeap.add(0); 
	}

	// 삽입
	public void insert(int value) {
		int parent;
		int tmp;
		
		minHeap.add(value);
		parent = minHeap.size() - 1;

		while (parent > 1 && minHeap.get(parent / 2) > minHeap.get(parent)) {
			tmp = minHeap.get(parent / 2);
			minHeap.set(parent / 2, minHeap.get(parent));
			minHeap.set(parent, tmp);
	
			parent = parent / 2;
		}
	}

	// 삭제
	public int delete() {
		int deleteN;
		int min;
		int minP;
		int tmp;
		
		if (minHeap.size() - 1 < 1) {
			return 0;
		}

		deleteN = minHeap.get(1);
		
		minHeap.set(1, minHeap.get(minHeap.size() - 1));
		minHeap.remove(minHeap.size() - 1);

		int pos = 1;
		while ((pos * 2) < minHeap.size()){
			
			min = minHeap.get(pos * 2);
			minP = pos * 2;

			if (((pos * 2 + 1) < minHeap.size()) && min > minHeap.get(pos * 2 + 1)) {
				min = minHeap.get(pos * 2 + 1);
				minP = pos * 2 + 1;
			}
			if (minHeap.get(pos) < min) {
				break;
			}

			tmp = minHeap.get(pos);
			minHeap.set(pos, minHeap.get(minP));
			minHeap.set(minP, tmp);
			pos = minP;
		}
		
		return deleteN;
	}

    public static void main(String[] args) {
    	
    	MinHeap heap = new MinHeap();

		heap.insert(1);
		heap.insert(2);
		heap.insert(3);
    		System.out.println(heap.delete());
    		System.out.println(heap.delete());
    		System.out.println(heap.delete());
    }
	
}

 

• 최대 힙 (Max Heap)

public class MaxHeap {

	private ArrayList<Integer> maxHeap;

	public MaxHeap() {
		maxHeap = new ArrayList<>();
		maxHeap.add(1000000); 
	}

	// 삽입
	public void insert(int value) {
		int parent;
		int tmp;
		
		maxHeap.add(value);
		parent = maxHeap.size() - 1;

		while (parent > 1 && maxHeap.get(parent / 2) < maxHeap.get(parent)) {
			tmp = maxHeap.get(parent / 2);
			maxHeap.set(parent / 2, maxHeap.get(parent));
			maxHeap.set(parent, tmp);
	
			parent = parent / 2;
		}
	}

	// 삭제
	public int delete() {
		int deleteN;
		int max;
		int maxP;
		int tmp;
		
		if (maxHeap.size() - 1 < 1) {
			return 0;
		}

		deleteN = maxHeap.get(1);
		
		maxHeap.set(1, maxHeap.get(maxHeap.size() - 1));
		maxHeap.remove(maxHeap.size() - 1);

		int pos = 1;
		while ((pos * 2) < maxHeap.size()){
			
			max = maxHeap.get(pos * 2);
			maxP = pos * 2;

			if (((pos * 2 + 1) < maxHeap.size()) && max < maxHeap.get(pos * 2 + 1)) {
				max = maxHeap.get(pos * 2 + 1);
				maxP = pos * 2 + 1;
			}
			if (maxHeap.get(pos) > max) {
				break;
			}

			tmp = maxHeap.get(pos);
			maxHeap.set(pos, maxHeap.get(maxP));
			maxHeap.set(maxP, tmp);
			pos = maxP;
		}
		
		return deleteN;
	}

    public static void main(String[] args) {
    	
    	MaxHeap heap = new MaxHeap();

		heap.insert(1);
		heap.insert(2);
		heap.insert(3);
    		System.out.println(heap.delete());
    		System.out.println(heap.delete());
    		System.out.println(heap.delete());
    }
}