Heap

Heap

• 힙은 자료구조의 일종으로 우선 순위 큐를 위해 만들어졌다.
• 우선 순위 큐 : 우선순위의 개념에 큐를 도입한 자료구조
  • 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져 나간다.
  • 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 등에 사용된다.
  • 우선 순위 큐는 배열, 연결 리스트, 힙으로 구현한다.

개념

• Tree의 형식을 취하고 있으면 Tree 중에서도 배열을 기반으로 한 완전 이진 트리(Complete Binary Tree)이다
• 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다.
• 중복된 값을 허용. (이진 탐색 트리는 중복 값을 허용하지 않음)
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.

힙 종류

최대 힙(max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

최소 힙(min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하지 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

부모 노드와 자식 노드 관계

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

힙의 삽입

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

void insert_max_heap(int x) {

    // 힙 크기를 하나 증가하고, 마지막 노드에 x를 넣음
    maxHeap[++heapSize] = x;

    for (int i = heapSize; i > 1; i /= 2) {
        // 마지막 노드가 자신의 부모 노드보다 크면 swap
        if (maxHeap[i/2] < maxHeap[i]) {
            swap(i/2, i);
        } else {
            break;
        }
    }
}

부모 노드는 자식 인덱스의 /2 이므로, 비교하고 자신이 더 크면 swap하는 방식

힙의 삭제

• 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제됨

  • 최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것

• 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴

• 힙을 재구성

  int delete_max_heap() {
  // 배열이 비어있으면 리턴
  if (heapSize == 0) return 0;
  
  int item = 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;
      } else if (maxHeap[i*2] > maxHeap[i*2+1]) {
        // 왼쪽 노드가 더 큰 경우, swap
        swap(i, i*2);
      } else {
          // 오른쪽 노드가 더 큰 경우
          swap(i i*2+1);
          i = i*2+1;
      }
  }
  return item;
  }