Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 바이너리 힙(Binary Heap) 구현하기: 삽입·삭제·최솟값 추출까지

바이너리 힙(Binary Heap)이란?

바이너리 힙은 최소 힙(Min Heap) 또는 최대 힙(Max Heap) 중 하나의 성질을 만족하는 완전 이진 트리(Complete Binary Tree)입니다. 최대 힙에서는 루트 노드의 키가 힙에 존재하는 모든 키 중에서 가장 커야 하며, 이 규칙은 트리의 모든 노드에 대해 재귀적으로 성립해야 합니다. 반대로 최소 힙에서는 루트 노드가 항상 최솟값을 가집니다.

힙은 일반적으로 배열(여기서는 vector)을 기반으로 구현하며, 우선순위 큐를 효율적으로 처리하는 데 널리 활용됩니다. 이 글에서 다루는 연산의 시간 복잡도는 다음과 같습니다.

  • 원소 삽입(Insert): O(log n)
  • 최솟값 삭제(DeleteMin): O(log n)
  • 최솟값 확인(ExtractMin): O(1)

주요 함수 설명

  • void BHeap::Insert(int ele): 힙에 새로운 원소를 삽입하는 연산을 수행합니다.
  • void BHeap::DeleteMin(): 힙에서 최솟값(루트)을 삭제하는 연산을 수행합니다.
  • int BHeap::ExtractMin(): 힙의 최솟값을 반환하는 연산을 수행합니다.
  • void BHeap::showHeap(): 현재 힙에 저장된 모든 원소를 화면에 출력합니다.
  • void BHeap::heapifyup(int in): 삽입 후 아래에서 위로(bottom-up) 올라가면서 힙 구조를 유지합니다.
  • void BHeap::heapifydown(int in): 삭제 후 위에서 아래로(top-down) 내려가면서 힙 구조를 유지합니다.

C++ 예제 코드

아래 프로그램은 vector를 기반으로 최소 바이너리 힙 클래스 BHeap을 구현하고, 메뉴 방식으로 각 연산을 직접 테스트할 수 있도록 작성되었습니다.

#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
class BHeap {
   private:
   vector <int> heap;
   int l(int parent);
   int r(int parent);
   int par(int child);
   void heapifyup(int index);
   void heapifydown(int index);
   public:
      BHeap() {}
      void Insert(int element);
      void DeleteMin();
      int ExtractMin();
      void showHeap();
      int Size();
};
int main() {
   BHeap h;
   while (1) {
      cout<<"1.Insert Element"<<endl;
      cout<<"2.Delete Minimum Element"<<endl;
      cout<<"3.Extract Minimum Element"<<endl;
      cout<<"4.Show Heap"<<endl;
      cout<<"5.Exit"<<endl;
      int c, e;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter the element to be inserted: ";
            cin>>e;
            h.Insert(e);
         break;
         case 2:
            h.DeleteMin();
         break;
         case 3:
            if (h.ExtractMin() == -1) {
               cout<<"Heap is Empty"<<endl;
            }
            else
            cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
         break;
         case 4:
            cout<<"Displaying elements of Heap: ";
            h.showHeap();
         break;
         case 5:
            exit(1);
         default:
            cout<<"Enter Correct Choice"<<endl;
      }
   }
   return 0;
}
int BHeap::Size() {
   return heap.size();
}
void BHeap::Insert(int ele) {
   heap.push_back(ele);
   heapifyup(heap.size() - 1);
}
void BHeap::DeleteMin() {
   if (heap.size() == 0) {
      cout<<"Heap is Empty"<<endl;
      return;
   }
   heap[0] = heap.at(heap.size() - 1);
   heap.pop_back();
   heapifydown(0);
   cout<<"Element Deleted"<<endl;
}
int BHeap::ExtractMin() {
   if (heap.size() == 0) {
      return -1;
   }
   else
   return heap.front();
}
void BHeap::showHeap() {
   vector <int>::iterator pos = heap.begin();
   cout<<"Heap --> ";
   while (pos != heap.end()) {
      cout<<*pos<<" ";
      pos++;
   }
   cout<<endl;
}
int BHeap::l(int parent) {
   int l = 2 * parent + 1;
   if (l < heap.size())
      return l;
   else
      return -1;
}
int BHeap::r(int parent) {
   int r = 2 * parent + 2;
   if (r < heap.size())
      return r;
   else
      return -1;
}
int BHeap::par(int child) {
   int p = (child - 1) / 2;
   if (child == 0)
      return -1;
   else
      return p;
}
void BHeap::heapifyup(int in) {
   if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
      int temp = heap[in];
      heap[in] = heap[par(in)];
      heap[par(in)] = temp;
      heapifyup(par(in));
   }
}
void BHeap::heapifydown(int in) {
   int child = l(in);
   int child1 = r(in);
   if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) {
      child = child1;
   }
   if (child > 0 && heap[in] > heap[child]) {
      int t = heap[in];
      heap[in] = heap[child];
      heap[child] = t;
      heapifydown(child);
   }
}

실행 결과

1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 3
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 7
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 6
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Heap: Heap --> 2 3 7 6
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 3
Minimum Element: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 2
Element Deleted
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Heap: Heap --> 3 6 7
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 5

결과 해설

위 실행 예시에서는 2, 3, 7, 6을 차례대로 삽입한 후 힙 전체를 출력하면 "2 3 7 6" 순서로 저장되어 있음을 확인할 수 있습니다. 최소 힙의 특성상 루트에는 항상 최솟값인 2가 위치하며, ExtractMin을 호출하면 이 값이 그대로 반환됩니다.

이후 DeleteMin으로 루트를 삭제하면 힙의 마지막 원소가 루트로 이동한 뒤 heapifydown이 실행되어 힙이 재정렬됩니다. 그 결과 힙은 "3 6 7" 상태가 되며, 여전히 루트(3)가 남은 원소들 중 최솟값임을 알 수 있습니다. 이처럼 힙은 삽입과 삭제 시에도 스스로 구조를 복원하기 때문에 우선순위 기반 데이터 처리에 매우 효율적인 자료구조입니다.