[알고리즘] 12 - 힙을 마스터하자

1. 힙 소개

2. 삽입(최대 힙)

void Insert(int arr[], int i){
  while(i > 0 && arr[i/2] < arr[i]){

    // Swapping parent and current  
    swap(arr[i/2], arr[i]);

    // Move on to the next element
    i = i/2;
  }
}

3. 삭제(최대 힙)

void deleteRoot(int arr[], int& n)
{
    // Get the last element
    int lastElement = arr[n - 1];

    // Replace root with last element
    arr[0] = lastElement;

    // Decrease size of heap by 1 (element deleted)
    n = n - 1;

    // Start from the bottom
    int i = n;

    // Construct the heap again after the deletion
    while(true){

      // After we proceed the root node, break out of the loop.
      if(i < 0)break;

      // Compare two children and swap
      if(i*2 <= n && arr[i] < arr[i*2]){
        swap(arr[i], arr[i*2]);
      } else if(arr[i] < arr[i*2+1]){
        swap(arr[i], arr[i*2+1]);
      }

      i--;
   }
}

4. 힙 정렬

5. 히피파이

6. C++에서 힙을 사용하는 방법