Heap

최대 힙을 구현해보자

힙은 이진트리로 구현하는 우선순위 큐 이다. (이진트리는 배열로)

삽입 O(lgN), 삭제 O(lgN)

 

힙의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.
2. 새로운 노드를 부모 노드들과 교환한다.

static void add(int x){
	tree[++size] = x;
    
    	int idx=size;
    	while(idx >1){
		if(tree[idx] < tree[idx/2]) swap(idx, idx/2);
        	else break;
        
        	idx /=2;
	}
}

힙의 삭제

1. 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것)
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
3. 힙을 재구성

static int remove(){
	if(size == 0) return 0;
	int top = tree[1]

	tree[1] = tree[size];
	tree[size--] = 0;

	int idx = 1;
	while(idx*2 <= size){
		int l=idx*2, r=idx*2+1;

		if((r>size || tree[l] < tree[r]) && tree[idx] > tree[l]){
			swap(idx, l);
			idx = l;
		}
		else if(r <= size && tree[idx] > tree[r]){
			swap(idx, r);
			idx = r;
		}
		else break;
	}

	return top;
}

이미지 출처: velog.io/@emplam27/자료구조-그림으로-알아보는-힙Heap

 

 

파이썬에서는

import heapq
q=[]
heappush(q,(0,start))
d,now=heqpq.heappop(q)
...
print(heap)  # (내부 구조는 힙 특성만 만족)

data = [5, 2, 8, 1, 3]
heapq.heapify(data) -> q는 list여야만한다.
print(data)  # [1, 2, 8, 5, 3] (힙 구조로 재배치됨)
print(heapq.heappop(data))  # 1