힙(heap)

힙

• 기본 배열로 구성
• 편의를 위해 인덱스를 1부터 시작
• 기본 완전 이진 트리 형태를 사용
• 최대힙을 기준으로 설명

삽입

• 가장 마지막 인덱스 n + 1에 삽입
• n + 1의 부모와 계속 비교해나가며, 값이 크면 (부모의 값이 작으면) 교환한다.

void insert(){
	maxHeap[++heapSize] = x;
	
	for (int i = heapSize; i > 1; i /= 2){
		if (maxHeap[i / 2] < maxHeap[i]){
			swap(i/2, i);
		}
		else{
			break;
		}
	}
}

삭제

int deleteMaxHeap(){
	if (heapSize == 0){
    	return 0;
    }
    
    // 1번째 인덱스가 root임.
    // 1. 루트 노드를 poll한다.
    int root = maxHeap[1]; 
    // 2. 마지막 노드의 요소를 루트에 삽입한다.
    maxHeap[1] = maxHeap[heapSize];
    // 3. 힙을 재배치한다.
    // 자식들과 대소관계를 비교하며 내려간다. (O(logN))
    for (int i = 1; i * 2 <= heapSize;){
    	// 3-1. 마지막 노드의 값이 두자식보다 모두 큰 경우 : 그냥 break;
    	if (maxHeap[i] > maxHeap[i * 2] && maxHeap[i] > maxHEap[i * 2 + 1]){
        	break;
        }
        // 3-2. 왼쪽노드가 더 큰경우 : swap
        else if (maxHeap[i] < maxHeap[i * 2]){
        	swap(i, i * 2);
            i = i * 2; // 인덱스 왼쪽 자식으로
        }
        else if (maxHeap[i] < maxHeap[i * 2 + 1]){
        	swap(i, i * 2 + 1);
            i = i * 2 + 1;
        }
    }
}

참고, 출처

• github
  tech-interview-for-developer : 자료구조 - 힙