[data structure] heap

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. <힙의 삽입=""> - 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입. - 새로운 노드를 검사해서 부모 노드와 교환한다. [최대 힙 삽입 구현] ```java 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. <힙의 삭제=""> - 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제된다. (최대 힙에서 삭제 연산은 최대값 요소를 삭제하는 것이다.) - 삭제된 루트 노드에서는 힙의 마지막 노드를 가져온다. - 힙을 재구성 한다. [최대 힙 삭제 구현] ```java 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와 교체하고 교체할 노드가 없을 때까지 반복한다. [MIT 라이선스에 따른 출처 표기](https://github.com/WooVictory/Ready-For-Tech-Interview)