힙

힙 특징

• 완전 이진 트리를 기초로 하는 자료구조이다.
  • 완전 이진 트리 : 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리
• 힙의 종류
  • 최대힙 : 부모노드의 값이 자식노드의 값보다 항상 크거나 같다. (위 그림이 예시)
  • 최소힙 : 부모노드의 값이 자식노드의 값보다 항상 작거나 같다.
• 중복값을 허용한다.
  • 최댓값이나 최솟값을 쉽게 뽑기 위한 자료구조이므로, 중복을 허용한다.
• 반정렬 상태 (느슨한 정렬 상태)
  • 모든 요소들이 정렬되어 있지는 않지만 부모노드가 무조건 자식노드보다 크거나 작기 (같을수도) 때문에, 반정렬 상태라고 한다.

사용처

• 우선순위 큐
  • 우선순위 개념을 큐에 도입한 자료구조
  • 데이터들이 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 나간다.

구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 배열의 첫번째 인덱스인 0은 사용하지 않는다.
  • 구현의 편의성 때문에
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
  • ex) 루트노드(1)의 오른쪽 노드 번호는 항상 3이다.

부모 노드와 자식 노드 관계

• 왼쪽 자식 index = (부모 index) * 2
• 오른쪽 자식 index = (부모 index) * 2 + 1
• 부모 index = (자식 index) / 2

힙 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.
2. 삽입된 노드를 아래 규칙에 따라 부모 노드와 교체한다.
   • 최대힙인 경우 : 부모 노드보다 크다면 교체 (반복)
   • 최소힙인 경우 : 부모 노드보다 작다면 교체 (반복)

최대힙 삽입 구현

public void insertMaxHeap(int x) {
	//힙 크기 1 증가 후, 해당 위치에 x 삽입
	maxHeap[++heapSize] = x;

	//(자식index) / 2 = (부모index)
	for (int i = heapSize; i > 1; i /= 2) {
		int parentValue = maxHeap[i/2];
		int newValue = maxHeap[i];

		//새로 삽입된 노드가 자신의 부모 노드보다 크면 서로 교체
		if (parentValue < newValue) swap(i/2, i);
		else break;
	}
}

• (자식index) / 2 = (부모index) 임을 활용하여, 부모노드와 교체하는 방식

힙 삭제

• 최대힙인 경우
  1. 최대값인 루트노드를 삭제
     • 최대힙에서의 삭제 연산 == 최대값 요소를 제거
  2. 삭제된 루트노드 위치에 힙의 마지막 노드를 가져옴
  3. 힙 재구성 (다시 최대힙을 만드는 것)
     • 왼쪽·오른쪽 자식노드 중 작은 자식노드와 교체
• 최소힙인 경우
  1. 최소값인 루트노드를 삭제
     • 최소힙에서의 삭제 연산 == 최소값 요소를 제거
  2. 삭제된 루트노드 위치에 힙의 마지막 노드를 가져옴
  3. 힙 재구성 (다시 최소힙을 만드는 것)
     • 왼쪽·오른쪽 자식노드 중 작은 자식노드와 교체

최대힙 삭제 구현

public int deleteMaxHeap() {
	if (heapSize == 0) return 0; //배열이 비어있으면 0 리턴
	
	int maxValue = maxHeap[1]; //루트 노드 값 저장
	maxHeap[1] = maxHeap[heapSize]; //마지막 노드 값을 루트 노드로
	maxHeap[heapSize--] = 0; //마지막 노드를 교체했으므로, 값을 0으로 초기화하고 heapSize를 1 감소
	
	for (int i = 1; i*2 <= heapSize;) {
		//마지막 노드(삭제된 노드 위치로 들어간 노드)가 왼쪽 노드와 오른쪽 노드보다 크면 종료
		if (maxHeap[i] > maxHeap[i*2] && maxHeap[i] > maxHeap[i*2+1]) break;

		//왼쪽 노드가 오른쪽 노드보다 더 큰 경우, 왼쪽 노드 선택
		else if (maxHeap[i*2] > maxHeap[i*2]) {
			swap(i, i*2);
			i = i*2;
		}

		//오른쪽 노드가 왼쪽 노드보다 더 큰 경우, 오른쪽 노드 선택
		else {
			swap(i, i*2+1);
			i = i*2+1;
		}
	}

	return maxValue;
}

• 만약 왼쪽·오른쪽 자식 노드가 부모 노드보다 모두 크다면, 더 큰 자식 노드와 교체해야 한다.
  • 왼쪽(4), 오른쪽(10) 인 경우 왼쪽 노드와 변경한다면, (4)가 (10)의 부모노드가 되므로 최대힙을 구성하지 못한다.