[Data Structure] Heap.md

Heap

1. 개요
2. 개념

힙은 자료구조의 일종으로 우선 순위 큐를 위해서 만들어졌다.

• 우선 순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조.

  • 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져 나간다.

• 언제 사용?

  • 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산.
  • 우선 순위 큐는 배열, 연결 리스트, 힙으로 구현한다. (힙으로 구현하는 게 가장 효율적이다.)

• 시간 복잡도

  • 삽입 : O(logN)
  • 삭제 : O(logN)

• 스택 : LIFO, 큐 : FIFO

[개념]

• Tree의 형식을 취하고 있으며 Tree 중에서도 배열을 기반으로 한 (Complete Binary Tree)완전 이진 트리이다.
• 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다.
• 배열에 트리의 값을 넣어줄 때는 0번째는 건너뛰고 1번째부터 루트 노드가 시작된다. 이유는 노드의 고유 번호와 index를 일치시켜 혼동을 줄이기 위함이다.
• 중복된 값을 허용. (이진 탐색 트리는 중복 값을 허용하지 않음.)
• 힙의 종류로는 최대힙과 최소힙이 존재한다.
  • 최대힙 : 각 노드의 값이 자식 노드의 값보다 크거나 같은 Complete Binary Tree를 말한다.
  • 최소힙은 최대힙의 반대이다.
  • 최대힙에서는 Root Node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.
  • Complete Binary Tree이기 때문에 배열을 이용해 관리할 수 있으며, 인덱스를 통한 Random Access가 가능하다.
  • Index 번호는 노드 개수가 n개일 때, i번째 노드에 대하여 왼쪽 자식은 ix2, 오른쪽 자식은 ix2+1가 된다.

구현

힙을 저장하는 표준적인 자료구조는 배열이다.

구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않고, 1부터 시작한다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

<부모 노드와 자식 노드의 관계>

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

1. <힙의 삽입>

• 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입.
• 새로운 노드를 검사해서 부모 노드와 교환한다.

[최대 힙 삽입 구현]

void insert_max_heap(int x){
  maxHeap[++heapSize] = x;
  // 힙 크기를 하나 증가시키고, 마지막 노드에 x를 삽입.
  
  for(int i=heapSize; i>1; i--){
    // 마지막 노드가 자신의 부모 노드보다 크면 swap
    if(maxHeap[i / 2] < maxHeap[i]){
      swap(i / 2, i);
    } else {
      break
    }
  }
}

부모 노드 : 자신의 인덱스 / 2 이므로 마지막 노드와 비교하여 마지막 노드가 더 크면 위치를 바꿔준다.

2. <힙의 삭제>

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

[최대 힙 삭제 구현]

int delete_map_heap(){
  if(heapSize == 0) return 0; // 비어있음을 의미하므로 리턴.
  
  int root = maxHeap[1]; // 루트 노드의 값을 저장.
  maxHeap[1] = maxHeap[heapSize]; // 마지막 노드를 루트 노드로 이동.
  maxHeap[heapSize--] = 0; // 힙 크기를 하나 줄이고 마지막 노드를 0으로 초기화.
  
  // 힙을 구현하는 배열을 정렬하는 부분.
  for(int i=1; i*2 <= heapSize;){
    // 마지막 노드가 왼쪽 노드와 오른쪽 노드보다 크면 끝. 
    if(maxHeap[i] > maxHeap[i * 2] && maxHeap[i] > maxHeap[i * 2 + 1]){
      break;
      // 왼쪽 노드가 더 큰 경우, swap
    } else if(maxHeap[i * 2] > maxHeap[i * 2 + 1]){
      swap(i, i * 2);
      i = i * 2;
      // 오른쪽 노드가 더 큰 경우, swap
    } else {
      swap(i, i * 2 + 1);
      i = i * 2 + 1;
    }
  }
  
  return root;
}

Heapify

• 두 개의 서브 트리가 최대힙(최소힙)일 때, root를 포함하는 전체가 heap이 되도록 위치를 조정하는 과정을 말한다.
• 루트에서 작은 값이 흘러 내려가면서 처리되는 방식으로 진행된다. 최대힙의 경우 root가 child보다 작으면 두 개의 child node 중 값이 큰 노드를 root와 교체하고 교체할 노드가 없을 때까지 반복한다.