Heap

 

 

Heap

 

- 우선 순위 큐 및 대기열을 만드는데 사용되어진다 (우선순위 큐를 구현할 때 가장 효율적이다)

- 완전 이진 트리의 일종이다(가질 수 있는 노드의 최댓값은 2^(k+1)  -  1이다)

- 반정렬 상태를 유지한다

- 삽입/삭제는 O(logN)으로 매우 빠르다 

- 배열의 자료구조로 저장된다 

- 첫 index인 0은 사용되지 않는다

- Heap 정렬은 선택정렬의 원리를 가진다

 

 

 

종류

1. 최대heap - 부모노드가 자식노드보다 크다
2. 최소heap - 부모노드가 자식노드보다 작음 

 

삽입

 

Heap에 데이터가 추가 되는 경우는 크게 2가지로 나뉜다.

 

1. Comparator가 nul이 아닐 때

2. Comparator가 null일 때  

 

기본적으로 맨 밑 자식 노드에 값이 하나 추가되는 경우를 생각해보자. 

 

1. 삽입된 노드와 부모 노드의 값을 비교한다. 

2. 만약 부모 노드가 값이 더 크다면, 두 값을 변경한다

3. 변경한 위치에서의 부모노드와 해당 노드 값을 비교한다

4. 부모 노드의 값이 더 크면 값을 두 값을 변경한다.

5. 이와 같은 과정을 반복하다가 부모 노드의 값이 더 크지 않을 때 종료한다

 

위와 같은 과정(최소heap)을 상향 선별이라고 부른다 

반대의 과정(최대 heap)을 하향 선별이라고 부른다

 

삭제

 

1. 최대 heap일 때

1. 최대 값인 루트 노드를 삭제한다 
2. 마지막 index 노드를 루트 노드로 가져온다
3. 자식 값이 더 크다면 교환한다
4. 3의 과정 반복

코드예시)

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;
       }
  // 왼쪽 노드가 더 큰 경우, 왼쪽 노드와 마지막 노드를 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 item;
}

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

 

2. 최소 heap일 때

1. 최소 값인 루트 노드를 삭제한다
2. 마지막 index 노드를 루트 노드로 가져온다
3. 자식 값이 더 작으면 교환한다
4. 3의 과정을 반복한다

내가 직접 구현한 코드)

int delete_min_heap(){
  if(heapSize==0){
    return 0;
  }
  int rootnode = minheap[1];
  //index 0 에는 아무 것도 대입하지 않기 때문이다 
  minheap[1] = minheap[heapSize];
  minheap[heapSize--] = 0; 
  //마지막 노드가 0이 되고, heapSize가 감소된다 
  for(int i=1 ; i*2<=heapSize;){
    //index마지막까지 가되, 자식 노드로 가면 i*2가 되어야함
    if(minheap[i] < minheap[i*2] && minheap[i] < minheap[i*2+1]{
      break;
    }
    else if (minheap[i*2] < minheap[i*2+1]){
               swap(i, i*2+1);
               i = i*2+1;
      
    }
    else {
      swap(i, i*2);
      i = i*2;
     }
    
  
  
  }
  

}